HDU 2546 饭卡（背包）

饭卡

思路：先把最贵的一个拿出来，剩下的用背包求出最优解，用5元去买最贵的。
 1 #include <map>
 2 #include <queue>
 3 #include <stack>
 4 #include <math.h>
 5 #include <stdio.h>
 6 #include <string.h>
 7 #include <iostream>
 8 #include <algorithm>
 9 #define LL long long
10 using namespace std;
11 
12 void run()
13 {
14     int n, m;
15     int a[1010], dp[1010];
16     while(~scanf("%d", &n) && n)
17     {
18         int max = 0, t;
19         memset(dp, 0, sizeof(dp));
20         for(int i = 1; i <= n; i++)
21         {
22             scanf("%d", &a[i]);
23             if(a[i] > max)
24             {
25                 max = a[i];
26                 t = i;
27             }
28         }
29         scanf("%d", &m);
30         for(int i = 1; i <= n; i++)
31         {
32             if(i != t)
33             {
34                 for(int j = m-5; j >= a[i]; j--)
35                 {
36                     if(dp[j] < dp[j-a[i]]+a[i])
37                         dp[j] = dp[j-a[i]]+a[i];
38                 }
39             }
40         }
41         int Max = 0;
42         for(int i = 1; i <= m-5; i++)
43         {
44             if(Max < dp[i])
45                 Max = dp[i];
46         }
47         if(m >= 5)
48             printf("%d
", m-Max-max);
49         else
50             printf("%d
", m);
51     }
52 }
53 
54 int main(void)
55 {
56     run();
57 
58     return 0;
59 }
饭卡