Hdu 2546 饭卡(DP_背包)

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

解题思路：本题可套用01背包的思想，值是价值变为可达不可达。用dp[j]表示余额为j是否可达，可达为1，否则为0.状态转移方程为 if (dp[j] && j - price[i] >= 5) dp[j-price[i]] = 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[i]); 
        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[i] >= 5)  
                        dp[j-price[i]] = 1; 
                    if (j - price[i] < minn) 
                        minn = j - price[i]; 
                } 
 
 
        printf("%d/n",minn); 
    } 
} 

摘自 ZeroClock