POJ1276

Posted on | In ,

Cash Machine

Solution sketch

有限背包問題，需要使用二進制拆解！（請看解說）

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
using namespace std;
typedef pair<int, int> ii;
int dp[2][111111];
int main()
{
    int total, n;
    while (scanf("%d %d", &total, &n) == 2) {
        // read input
        vector<ii> coins;
        for (int i = 0; i < n; i++) {
            int cnt, val;
            scanf("%d %d", &cnt, &val);
            coins.push_back(ii(val, cnt));
        }
        /*
        printf("%d %d\n", total, n);
        for(int i = 0; i < n; i++) {
                printf("%d %d\n", coins[i].first, coins[i].second);
        }
        */
        // DP
        memset(dp, 0, sizeof(dp));
        // convert to log(n)
        vector<int> data;
        data.push_back(-1);
        for (int i = 0; i < n; i++) {
            int val = coins[i].first;
            int cnt = coins[i].second;
            int sum = 0;
            for (int j = 0; (1 << j) + sum <= cnt;
                 j++) { // split the coeff and make sure the sum won't exceed cnt
                data.push_back(val * (1 << j));
                sum += (1 << j);
            }
            if (sum != cnt)
                data.push_back(val * (cnt - sum));
        }
        for (int i = 1; i < (int)data.size(); i++) {
            for (int j = 0; j <= total; j++) {
                if (j - data[i] >= 0)
                    dp[i % 2][j] =
                        max(dp[(i % 2) ^ 1][j - data[i]] + data[i], dp[(i % 2) ^ 1][j]);
                else
                    dp[i % 2][j] = dp[(i % 2) ^ 1][j];
            }
        }
        printf("%d\n", dp[n % 2][total]);
    }
    return 0;
}