【HDOJ】2546 饭卡

01背包，需要先对数据升序排序。这样保证优先购买最贵的东西，才满足背包条件。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 
 5 #define MAXNUM 1005
 6 
 7 int prices[MAXNUM];
 8 int dp[MAXNUM];
 9 
10 int mymax(int a, int b) {
11     return a>b ? a:b;
12 }
13 
14 int comp(const void *a, const void *b) {
15     return *(int *)b - *(int *)a;
16 }
17 
18 int main() {
19     int n, m;
20     int i, j, tmp;
21 
22     while (scanf("%d", &n)!=EOF && n) {
23         for (i=1; i<=n; ++i) {
24             scanf("%d", &prices[i]);
25         }
26 
27         scanf("%d", &m);
28 
29         if (m < 5) {
30             printf("%d
", m);
31             continue;
32         }
33 
34         qsort(prices+1, n, sizeof(int), comp);
35         memset(dp, 0, sizeof(dp));
36 
37         for (i=1; i<=n; ++i) {
38             for (j=m; j>=5; --j) {
39                 tmp = j - prices[i];
40                 if (tmp >= 5) {
41                     dp[j] = mymax(dp[tmp]+prices[i], dp[j]);
42                 } else {
43                     dp[j] = mymax(prices[i], dp[j]);
44                 }
45             }
46         }
47 
48         printf("%d
", m-dp[m]);
49     }
50 
51     return 0;
52 }