题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2546
先找出最贵的那个菜，这个菜一定是最后买的那个。然后再在前n-1个菜里做01背包。找出不超过m-5的最大价值。然后用m减去这两个值即可。
1 #include <algorithm> 2 #include <iostream> 3 #include <iomanip> 4 #include <cstring> 5 #include <climits> 6 #include <complex> 7 #include <fstream> 8 #include <cassert> 9 #include <cstdio> 10 #include <bitset> 11 #include <vector> 12 #include <deque> 13 #include <queue> 14 #include <stack> 15 #include <ctime> 16 #include <set> 17 #include <map> 18 #include <cmath> 19 20 using namespace std; 21 22 //kirai 23 const int maxn = 1111; 24 int n, m; 25 int dp[maxn]; 26 int w[maxn]; 27 28 int main() { 29 // freopen("in", "r", stdin); 30 while(~scanf("%d", &n) && n) { 31 int maxx = -1; 32 int pos; 33 for(int i = 1; i <= n; i++) { 34 scanf("%d", &w[i]); 35 if(maxx < w[i]) { 36 maxx = w[i]; 37 pos = i; 38 } 39 } 40 swap(w[pos], w[n]); 41 scanf("%d", &m); 42 if(m < 5) { 43 printf("%d ", m); 44 continue; 45 } 46 memset(dp, 0, sizeof(dp)); 47 for(int i = 1; i < n; i++) { 48 for(int j = m - 5; j >= w[i]; j--) { 49 dp[j] = max(dp[j], dp[j-w[i]]+w[i]); 50 } 51 } 52 printf("%d ", m - maxx - dp[m-5]); 53 } 54 return 0; 55 }