题目大意：电子科大的食堂刷卡问题，如果卡上余额大等于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
#include
#include
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