Poj 1742: Coins

poj1742.md

Poj 1742: Coins

題目

分析

多重背包，但須優化。

原始想法會 TLE，時間複雜度為 O(N * M * max(C[i]))：

bool dp[i][w] = 使用前 i 個硬幣可不可以組出 w
dp[i][w] = any([dp[i-1][w - k * a[i]] for 0 <= k <= C[i]])
dp[0][0] = true

優化的方法為當成 無限背包 來做，但另外記錄硬幣的使用個數。

###定義

bool dp[w] = 可不可以組出 w
int num[w] = 組出 w 需使用幾個 A[i] 硬幣

答案為 count(dp + 1, dp + M + 1, true)

剩下的直接寫在程式碼的注釋裡。時間複雜度降到 O(N*M)

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int N, M;
int A[100];
int C[100];
bool dp[100000];
int num[100000];

int solve() {
    memset(dp, false, sizeof(dp));

    dp[0] = true;
    for (int i = 0; i < N; i++) {
        // num[j] 記錄組出 j 需使用幾個 **A[i]** 硬幣。
        memset(num, 0, sizeof(num));
        
        // j 從 A[i] 開始，當然。比 A[i] 小的，不可能用 A[i] 組出。
        for (int j = A[i]; j <= M; j++) {
            // 如果 j 尚無法組出，
            // 且 j - A[i] 可以組出，且硬幣數量沒有超過（至少還有一枚可以用）
            if (dp[j] == false && dp[j - A[i]] && num[j - A[i]] < C[i]) {
                dp[j] = true; // j 就可以組出
                num[j] = num[j - A[i]] + 1;
                // 組出 j 的硬幣數量為組出 j - A[i] 的數量再加一。
            }
        }
    }

    return count(dp + 1, dp + M + 1, true);
}

int main() {
    while (scanf("%d %d", &N, &M) != EOF) {
        if (N == 0 && M == 0) break;

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

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

    return 0;
}

TLE Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int N, M;
int A[100];
int C[100];
bool dp[100][100000];

int solve() {
    memset(dp, false, sizeof(dp));

    for (int c = 0; c <= C[0]; c++)
        dp[0][A[0] * c] = true;

    for (int i = 1; i < N; i++) {
        // dp[i][w] = any(dp[i-1][w - k * a[i]] for 0 <= k <= C[i])
        for (int w = 0; w <= M; w++) {
            dp[i][w] = false;
            for (int k = 0; k <= C[i]; k++) {
                if (w - k * A[i] < 0)
                    break;
                if (dp[i - 1][w - k * A[i]]) {
                    dp[i][w] = true;
                    break;
                }
            }
        }
    }

    return count(dp[N-1] + 1, dp[N-1] + M + 1, true);
}

int main() {
    while (scanf("%d %d", &N, &M) != EOF) {
        if (N == 0 && M == 0) break;

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

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

    return 0;
}