hihocoder_week195奖券兑换

题目链接： http://hihocoder.com/contest/hiho195/problem/1
解题思路：记一下背包问题的模板。
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int imax_n = 100005;
 5 int n, m;
 6 int f[imax_n];
 7 int w[imax_n], p[imax_n];
 8 map<int, int> mp;
 9 
10 void zeroOneBag(int weight, int value)
11 {
12     for (int j = m; j >= weight; --j)
13     {
14         f[j] = max(f[j], f[j-weight] + value);
15     }
16 }
17 
18 void completeBag(int weight, int value)
19 {
20     for (int j = weight; j <= m; ++j)
21     {
22         f[j] = max(f[j], f[j - weight] + value);
23     }
24 }
25 
26 void multiBag(int weight, int value, int z)
27 {
28     int k = z;
29     int b = 1;
30     if (k * weight >= m)
31     {
32         completeBag(weight, value);
33         return ;
34     }
35     while (k >= b)
36     {
37         zeroOneBag(b*weight, b*value);
38         k -= b;
39         b<<=1;
40 
41     }
42     if (k)
43         zeroOneBag(k*weight, k*value);
44 }
45 
46 int main()
47 {
48     scanf("%d%d", &n, &m);
49     for (int i = 0; i < n; ++i)
50     {
51         scanf("%d%d", &w[i], &p[i]);
52         mp[100 * w[i] + p[i]]++;
53     }
54     int ans = 0;
55     memset(f, 0, sizeof(f));
56     for (int i = 1; i <=10; ++i)
57     {
58         for (int j = 1; j <=10; ++j)
59         {
60             if (mp.find(i * 100 + j) == mp.end())
61             {
62                 continue;
63             }
64             else
65             {
66                 multiBag(i, j, mp[i * 100 + j]);
67             }
68         }
69     }
70     for (int i = 0; i <= m; ++i)
71     {
72         ans = max(ans, f[i]);
73     }
74     printf("%d
", ans);
75     return 0;
76 }