题目：
思想：
给你1 2 5价值的钱，数量有限，可以用多重背包问题求解。
算出总的钱数，当做背包容量。相当于给你1你可以买1价值的东西，
给你4你却只能买3价值的东西。所以显然到最后，如果dp[i] < i;说明
所给的钱数不可以购买。
代码：
1 #include<stdio.h> 2 #include<string.h> 3 4 5 int getmax(int x, int y){ 6 return x > y ? x : y; 7 } 8 9 int main(){ 10 int sumprice, price[3], num[3001], i, j, cout, dp[8001], k; 11 while(scanf("%d %d %d", &price[0], &price[1], &price[2]) && (price[0] || price[1] || price[2])){ 12 cout = 0; 13 k = 0; 14 sumprice = price[0] + 2 * price[1] + 5 * price[2]; 15 while(price[0] --){ 16 num[cout ++] = 1; 17 } 18 while(price[1] --){ 19 num[cout ++] = 2; 20 } 21 while(price[2] --){ 22 num[cout ++] = 5; 23 } 24 memset(dp, 0, sizeof(dp)); 25 for(i = 0; i < cout; i ++){ 26 for(j = sumprice; j >= num[i]; j --){ 27 dp[j] = getmax(dp[j], dp[j - num[i]] + num[i]); 28 } 29 } 30 for(i = 1; i <= sumprice; i ++){ 31 if(dp[i] < i){ 32 printf("%d\n", i); 33 k = 1; 34 break; 35 } 36 } 37 if(k == 0){ 38 printf("%d\n", sumprice + 1); 39 } 40 } 41 return 0; 42 }
原文：http://www.cnblogs.com/xiaoyeye/p/3738907.html
