Hdu 2546 饭卡(DP_背包)

题目大意：电子科大的食堂刷卡问题，如果卡上余额大等于5，那就可以随便打菜，即使打了鲍鱼等价格比余额多得多的菜。现在给出n个菜的单价，每个菜买一次，问最后卡上剩的余额最少为多少？

解题思路：本题可套用01背包的思想，值是价值变为可达不可达。用dp[j]表示余额为j是否可达，可达为1，否则为0.状态转移方程为 if (dp[j] ;; j - price >= 5) dp[j-price] = 1;然后记录转移到最小值，最后输出即可。本题有两个地方需要注意：1、遍历余额的顺序要从0到sum，这样转移的时候都是利用前一次的结果，因为sum是初状态和01背包里的0状态一样。 2、price必须事先经过排序，否则前面大的先转移到5以下，后面小的就没办法更新了。


测试数据：

3
10000 1 3
9
1
50
5
10
1 2 3 2 1 1 2 3 2 1
50
3
1 2 3
3

代码：[cpp] #include <stdio.h>  
#include <string.h>  
#include <algorithm>  
using namespace std;
#define MAX 100000  


int n,price[MAX];
int sum,minn,dp[MAX];


int main()
{
    int i,j,k,t;

    
    while (scanf("%d",;n) ,n) {

        for (i = 1; i <= n; ++i)
            scanf("%d",;price);
        scanf("%d",;sum);
        sort(price+1,price+1+n);


        memset(dp,0,sizeof(dp));
        dp[sum] = 1,minn = sum;
        for (i = 1; i <= n; ++i)
            for (j = 5; j <= sum; ++j)  
                if (dp[j] == 1)  {

                    if (j - price >= 5)  
                        dp[j-price] = 1;
                    if (j - price < minn)
                        minn = j - price;
                }


        printf("%d\n",minn);
    }
}


摘自 ZeroClock