HDU2546（转化为0

1.做题首先注意审题： 卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。这句话非常重要！

2.本题棵可以用贪心思想考虑最后一步：当余额>=5时，一定可以购买成功，余额<5无法购买。最后一次应该争取在离5元最近的地方购买最贵的东西。

翻译这句话即：求解容量为m-5（余额的最大容量）的0-1背包的最大花销。而且要将最贵的产品放在最后买。

3.由于上述1条，在计算2条前先判断，余额<5时直接输出余额：无法购买。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1005;
int n,m;
int num[maxn];
int dp[maxn];
int solve()
{memset(dp,0,sizeof(dp));sort(num,num+n);//将num[n-1]排除后的最大花销,背包总容量是m-5if(m<5)return m;for(int i=0; i<n-1; i++)for(int j=m-5; j>=num[i]; j--)dp[j]=max(dp[j],dp[j-num[i]]+num[i]);return m-dp[m-5]-num[n-1];
}
int main()
{while(~scanf("%d",&n),n){for(int i=0; i<n; i++)scanf("%d",&num[i]);scanf("%d",&m);printf("%d\n",solve());}return 0;
}