題目大意：電子科大的食堂刷卡問題，如果卡上余額大等於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
