链接：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
     
       3 #include
      
        4 #include
       
         5 #include
        
          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
         
          =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 }