POJ1742 Coins(男人八题)¶

keywords: DP

Coins¶

非常经典的男人八题，来自于楼教主LouTiancheng@POJ

这道题目非常想写一篇题解，是因为这题目困扰了我很久，一直没有思考清楚，并且也对各种做法不懂。后来慢慢懂了，做一个总结

方法1，多重背包，3 loops，TLE¶

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>

using namespace std;

const int N = 110, M = 1e5 + 10;

int a[N], c[N], n, m;
int dp[N][M];           //MLE 4e7B = 39062KB > 30000KB

int main(){
    while (cin >> n >> m){
        if (n == 0 && m == 0) break;

        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= n; i++) cin >> c[i];

        memset(dp, 0, sizeof dp);
        dp[0][0] = 1; 
        for (int i = 1; i <= n; i++)
            for (int j = 0; j <= m; j++)
                for (int k = 0; k <= c[i] && k * a[i] <= j; k++)
                    dp[i][j] |= dp[i - 1][j - k * a[i]];

        int ret = 0;
        for (int i = 1; i <= m; i++) ret += dp[n][i];

        cout << ret << '\n';
    }

    return 0;
}

方法2，使用01背包和完全背包进行优化，代码思路来源于背包九讲，卡常¶

#include <iostream>
#include <cstdio>
#include <string>

using namespace std;

const int N = 110, M = 1e5 + 10;

int a[N], c[N], n, m;
int dp[M];

void complete(int v){
    for (int j = v; j <= m; j++) dp[j] |= dp[j - v];
}

void zeroone(int v){
    for (int j = m; j >= v; j--) dp[j] |= dp[j - v];
}

int main(){
    while (cin >> n >> m){
        if (n == 0 && m == 0) break;

        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= n; i++) cin >> c[i];

        memset(dp, 0, sizeof dp);
        dp[0] = 1; 
        for (int i = 1; i <= n; i++){
            if (a[i] * c[i] >= m) complete(a[i]);
            else{
                int j = 1;
                while (j < c[i]){
                    zeroone(j * a[i]);
                    c[i] -= j;
                    j <<= 1;
                }

                if (c[i]) zeroone(c[i] * a[i]);
            }
        }

        int ret = 0;
        for (int i = 1; i <= m; i++) ret += dp[i];

        cout << ret << '\n';
    }

    return 0;
}

方法4，压成一维，继续超时¶

// 压缩空间，和TLE没关系，补充一下而已

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int dp[N];
int v[N], w[N], s[N], n, V;

int main(){
    cin >> n >> V;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= s[i]; j++)
            for (int k = V; k >= v[i]; k--)
                dp[k] = max(dp[k], dp[k - v[i]] + w[i]);

    cout << dp[V] << '\n';

    return 0;
}

方法5、6，利用bitset进行优化常数32¶

// 首先我们用bitset做正常的循环，会超时
// 但是用来理解bitset如何表示状态的

#include <bits/stdc++.h>

using namespace std;

const int N = 110, M = 1e5 + 10;

int n, m, a[N], c[N];
bitset<M> f;

void print(){
    for (int i = m; i >= 0; i--) cout << f[i];
    puts("");
}

int main(){
    while (cin >> n >> m){
        if (!n && !m) break;

        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= n; i++) cin >> c[i];
        f.reset();
        f.set(0);
        for (int i = 1; i <= n; i++)
            for (int j = 0; j < c[i]; j++){  // 移动了c[i]次，每次移动a[i]位
                f |= f << a[i];
            }

        int cnt = 0;
        for (int i = 1; i <= m; i++)
            if (f[i]) cnt++;

        cout << cnt << '\n';
    }

    return 0;
}

/*
这时候，我们来理解一下bitset

对于测试数据：
1 10
1 6
只有一种硬币，价值1，一共有6枚，m是10，问有几种面值可以被表示

00000000001 [这是初始状态，0可以被表示]
00000000011 [左移一位(因为价值1)得00000000010，或上上一个状态00000000001]
00000000111 [左移一位得00000000110，或上上一个状态00000000011]

后面的状态就不继续举例了，每次都移动a[i]位，这样就一点一点推出来有哪些面值可以被表示
*/

这个地方也是困扰我最久的，刚开始，我只知道bitset可以优化32，但不知道为啥这样左移（最大的困惑是，01背包优化后，确实应该是从右往左遍历，但是这个bitset右往左，是低位到高位，这和01背包的遍历顺序不搭嘎啊）（现在我终于明白了，原来刚开始是这样用bitset表示状态的，我们下面看优化，这个优化就是用了倍增思想处理的）

#include <bits/stdc++.h>

using namespace std;

const int N = 110, M = 1e5 + 10;

int n, m, a[N], c[N];
bitset<M> f;

int main(){
    while (cin >> n >> m){
        if (!n && !m) break;

        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= n; i++) cin >> c[i];
        f.reset();
        f.set(0);
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= c[i]; c[i] -= j, j <<= 1)
                f |= f << (j * a[i]);
            f |= f << (c[i] * a[i]);  // 还剩余一个零头，可能是0，也可能不是0
        }


        int cnt = 0;
        for (int i = 1; i <= m; i++)
            if (f[i]) cnt++;

        cout << cnt << '\n';
    }

    return 0;
}

方法7，完全背包+贪心，来源于lyd¶

// 该程序使用了完全背包模型中j的循环顺序，通过used数组实现多重背包中物品个数的限制。同时根据贪心策略，当且仅当dp[j]为0，不得不利用第i种硬币时，才执行转移，保证不会漏掉可行解。

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>

using namespace std;

const int N = 110, M = 1e5 + 10;

int a[N], c[N], n, m;
int dp[M], used[M];        

int main(){
    while (cin >> n >> m){
        if (n == 0 && m == 0) break;

        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= n; i++) cin >> c[i];

        memset(dp, 0, sizeof dp);
        dp[0] = 1; 
        for (int i = 1; i <= n; i++){
            memset(used, 0, sizeof used);
            for (int j = a[i]; j <= m; j++)
                if (!dp[j] && dp[j - a[i]] && used[j - a[i]] < c[i])
                    dp[j] = true, used[j] = used[j - a[i]] + 1;
        }

        int ret = 0;
        for (int i = 1; i <= m; i++) ret += dp[i];

        cout << ret << '\n';
    }

    return 0;
}

方法8，多重背包+单调队列优化¶

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10, M = 110;

int n, m;
int A[M], C[M];
int dp[N], g[N];
int q[N];

int main(){
    while (cin >> n >> m){
        if (!n && !m) break;

        for (int i = 1; i <= n; i++) scanf("%d", &A[i]);
        for (int i = 1; i <= n; i++) scanf("%d", &C[i]);

        memset(dp, 0, sizeof dp);
        dp[0] = 1;
        for (int i = 1; i <= n; i++){
            if (C[i] == 1){              // 按01背包模型
                for (int j = m; j >= A[i]; j--) dp[j] = max(dp[j], dp[j - A[i]]);
            }
            else if (C[i]*A[i] >= m){    // 按完全背包模型
                for (int j = A[i]; j <= m; j++) dp[j] = max(dp[j], dp[j - A[i]]);
            }
            else{                        // 按多重背包模型+单调队列
                for (int r = 0; r < A[i]; r++){
                    int hh = 0, tt = -1;
                    for (int k = r; k <= m; k += A[i]){
                        if (hh <= tt && q[hh] < k - C[i]*A[i]) hh++;
                        if (dp[k]) q[++tt] = k;
                        if (hh <= tt) dp[k] = 1;
                    }
                }   
            }
        }

        int cnt = 0;
        for (int i = 1; i <= m; i++) if (dp[i]) cnt++;

        printf("%d\n", cnt);
    }

    return 0;
}
// 下面是一个错误的代码，我们分析一下原因

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10, M = 110;

int n, m;
int A[M], C[M];
int dp[N], g[N];
int q[N];

int main(){
    while (cin >> n >> m){
        if (!n && !m) break;

        for (int i = 1; i <= n; i++) scanf("%d", &A[i]);
        for (int i = 1; i <= n; i++) scanf("%d", &C[i]);

        memset(dp, 0, sizeof dp);
        dp[0] = 1;
        for (int i = 1; i <= n; i++){
            if (C[i] == 1){              // 按01背包模型
                for (int j = m; j >= A[i]; j--) dp[j] = max(dp[j], dp[j - A[i]]);
            }
            else if (C[i]*A[i] >= m){    // 按完全背包模型
                for (int j = A[i]; j <= m; j++) dp[j] = max(dp[j], dp[j - A[i]]);
            }
            else{                        // 按多重背包模型+单调队列
                for (int r = 0; r < A[i]; r++){
                    int hh = 0, tt = -1;
                    for (int k = r; k <= m; k += A[i]){
                        if (hh <= tt && q[hh] < k - C[i]*A[i]) hh++;
                        if (hh <= tt) dp[k] = 1;   //【这个地方交换一下顺序】
                        if (dp[k]) q[++tt] = k;    // 如果这样，将发生无限传递，结果是面值全可以拼成
                    }
                }   
            }
        }

        int cnt = 0;
        for (int i = 1; i <= m; i++) if (dp[i]) cnt++;

        printf("%d\n", cnt);
    }

    return 0;
}

2021-12-29，可惜现在poj好像挂了，评测队列一直卡，不能评测代码做直观的分析对比了。

2021-12-29，可以去acwing评测，https://www.acwing.com/problem/cont