01背包的变形，因为当剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负；
那么我们只需要一开始将余额减去5，将价值最大的物品拿出，然后求出当此时所能购买的最大价值，再用m+5减去最大价值和价值最大的物品就得出最后的答案了；
#include<iostream> #include<algorithm> #include<string> #include<cstring> #include<map> #include<queue> #include<cmath> #include<stack> #include<vector> #include<cstdio> #define MAXN 33000 #define INF 0x3f3f3f3f #define lmid l,m,rt<<1 #define rmid m+1,r,rt<<1|1 #define ls rt<<1 #define rs rt<<1|1 #define Mod 1000000007 #define i64 __int64 using namespace std; int num[1005]; int dp[1005]; int main() { int n; while(scanf("%d",&n),n) { memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) scanf("%d",&num[i]); sort(num+1,num+1+n); int maxn=num[n]; int m; scanf("%d",&m); if(m<5) { cout<<m<<endl; continue; } m-=5; for(int i=1;i<n;i++) for(int j=m;j>=num[i];j--) dp[j]=max(dp[j],dp[j-num[i]]+num[i]); cout<<m+5-dp[m]-maxn<<endl; } return 0; }
