题目链接:Click here~~
题意:
中文题不解释。
解题思路:
由于最后5元钱可以买任何价值的物品,所以为了使余额最少,我们应该用这5元钱买最贵的物品。
于是问题转化成了容量为V-5,除去一个最贵物品的01背包问题。
#include <stdio.h> #include <string.h> #define N 1005 #define max(a,b) a > b ? a : b int V,dp[N]; void Bag_01(int c,int w) { for(int i=V-5;i>=c;i--) dp[i] = max(dp[i],dp[i-c]+w); } int main() { int n,w[N],mmax,loc; while(scanf("%d",&n),n) { mmax = loc = 0; memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) { scanf("%d",&w[i]); if(mmax < w[i]) mmax = w[i] , loc = i; } w[loc] = w[n] , w[n] = mmax; scanf("%d",&V); if(V < 5) printf("%d\n",V); else { for(int i=1;i<=n-1;i++) Bag_01(w[i],w[i]); printf("%d\n",V-dp[V-5]-w[n]); } } return 0; }