链接：http://acm.hdu.edu.cn/showproblem.php?pid=2546
思路：需要首先处理一下的的01背包，当饭卡余额大于等于5时，是什么都能买的，所以题目要饭卡余额最小，那预留5元（相当于饭卡余额为5）来买最贵的菜
然后对剩下n-1进行01背包dp才是正确的。但是还存在一个问题，那就饭卡初始余额小于5时，也要处理掉。
下面讲01背包（原型可以看大牛的背包九讲，本人也正在学习），定义dp[i][j]为买前i种菜品剩下j元时的最大消费值等于下面两中情况之一的值
有两种来源，对于第i种菜品，可买或者不买
1.买的话就是dp[i-1][j-p[i]]+p[i],前i-1种菜品剩j-p[i]元的最大消费值+第i种菜品的消费值
2.不买的话就是dp[i-1][j],前i-1种菜品剩j元的最大消费值
则状态转移方程为:
dp[i][j] = max(dp[i-1][j],dp[i-1][j-p[i]]+p[i])
我们看到i的状态是由i-1得来的，则可以用一维数组来降低空间复杂度
但是如果j顺序循环的话，j是由(i-1时的j和j-p[i])的得来，顺推的时候，j-p[i]这个状态已经发生了改变，不再是(i-1)时的了，而是i的状态了。
采用逆推明显可以避免覆盖问题
一维表示就是 dp[j] = max(dp[j],dp[j-p[i]]+p[i])
下面看代码吧
1 ///具体是先判断m是否小于5，大于等于5的话就按升序排序，对前n-1菜品，m-5的余额使用01背包dp 2 #include<stdio.h> 3 #include<algorithm> 4 #include<string.h> 5 #include<set> 6 using namespace std; 7 int dp[1010],p[1010]; 8 int main() 9 { 10 int n,m; 11 while(scanf("%d",&n)&&n) 12 { 13 for(int i = 0; i<n; i++) 14 scanf("%d",&p[i]); 15 scanf("%d",&m); 16 if(m<5) 17 { 18 printf("%d\n",m); 19 continue; 20 } 21 memset(dp,0,sizeof(dp)); 22 sort(p,p+n); 23 int maxv = p[n-1]; 24 for(int i = 0; i<n-1; i++) 25 for(int j = m-5; j>=a[i]; j--) 26 dp[j] = max(dp[j],dp[j-p[i]]+p[i]); 27 printf("%d\n",m-maxv-dp[m-5]); 28 } 29 return 0; 30 }
原文：http://www.cnblogs.com/jiachinzhao/p/4550644.html