hdoj2546 饭卡（DP，01背包）

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=2546

思路

首先要判断卡里的钱是不是大于等于5元，如果不足5元，直接输出余额；如果大于等于5元，则先留5元买最贵的菜max_dish，再用剩下的钱买剩余的菜（不包括最贵的菜），使得菜的总价最大，最大为max_value，max_dish+max_value就是使用卡里的钱所能买到菜的总价的最大值，5 -（max_dish+max_value）就是答案。

代码

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <vector>
 5 using namespace std;
 6 
 7 const int N = 1010;
 8 vector<int> v;
 9 int n;
10 int dp[N];
11 
12 int main()
13 {
14     //freopen("hdoj2546.txt", "r", stdin);
15     while(cin >> n && n)
16     {
17         v.clear();
18         int t;
19         for(int i=0; i<n; i++)
20         {
21             cin>>t;
22             v.push_back(t);
23         }
24         int m;
25         cin >> m;
26         if(m - 5 < 0)
27         {
28             cout<<m<<endl;
29             continue;
30         }
31 
32         sort(v.begin(), v.end());   //先排序
33         for(int i=0; i<n-1; i++)    //不包含最贵的菜
34         {
35             for(int j=m-5; j>=v[i]; j--)
36                 dp[j] = max(dp[j], dp[j-v[i]]+v[i]);
37         }
38         cout<<m-dp[m-5]-v[n-1]<<endl;
39     }
40     return 0;
41 }