悲催了..~~ 这道01背包的题目我wa 了好多遍，感受还是颇多的...
说是01背包，但是还是有一定的研制条件的。。。
首先当饭卡当中的钱不足5块的时候是不能消费的，所以就应该是原来的值。这里就wa 了很多遍啊s。
然后变通一下，要使得饭卡当中所剩余额最小，那么也就是说最大价格的那道菜要在最后买，这样才能得到最优解，
那么对于其他n-1道菜就是一个简单的0-1背包了，只是这儿有一个变通，那就是背包所能得到的价值和它所耗空间是一样的...
接下来就看代码好好体会了。。。
View Code 1 #include<iostream> 2 #include<stdio.h> 3 using namespace std; 4 int dp[1010],num[1010],visit[1010]; 5 int main() 6 { 7 int n,rest; 8 while(scanf("%d",&n)!=EOF&&n) 9 { 10 int pos=n,Maxvalue=0; 11 memset(visit,0,sizeof(visit)); 12 for(int i=0;i<n;i++) 13 { 14 scanf("%d",&num[i]); 15 if(num[i]>Maxvalue) 16 { 17 Maxvalue=num[i]; 18 visit[pos]=0; 19 pos=i; 20 visit[pos]=1; 21 } 22 } 23 scanf("%d",&rest); 24 if(rest<5){printf("%d\n",rest);continue;} 25 memset(dp,0,sizeof(dp)); 26 for(int i=1;i<=n;i++) 27 { 28 for(int j=rest-5;j>=num[i-1];j--) 29 { 30 if(visit[i-1])break; 31 if(dp[j]<dp[j-num[i-1]]+num[i-1]&&rest-dp[j-num[i-1]]-num[i-1]>=5) 32 { 33 dp[j]=dp[j-num[i-1]]+num[i-1]; 34 } 35 } 36 } 37 printf("%d\n",rest-dp[rest-5]-Maxvalue); 38 } 39 40 return 0; 41 } 42
转载于:https://www.cnblogs.com/nuoyan2010/archive/2012/09/01/2667095.html
