poj1742 布爾值型 多重背包

 題目連結：點選打開連結

題意：

一個人有許多種硬币: A1, A2, A3, A4 .....Ai (1 <= i <= n)；

每一種硬币有許多個: C1, C2, C3, C4 .....Ci (1 <= i <= n)；

問他可以用硬币組成多少種不超過 m 的價格；

了解：

這是樓教主的男人必過八題；

可惜了，自己做不來；

神解釋說是多重背包；

但是和書上的不一樣；

其實遞推式才是真正有用的東西；

遞推式含義：dp[i] 表示能否通過前面已求出來的确定價格推導出 i 這個價格；

即：dp[i] = (dp[i - A[i]] == 1)；

其中 A[i] 使用了的個數不能超過 C[i] 個；

代碼如下：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int MIN_INF = 1e-7;
const int MAX_INF = (1e9) + 7;

#define X first
#define Y second

int dp[100100], sum[100100];

int main() {
    int n, m;
    while (cin >> n >> m && n + m) {
        vector<int> a(n), c(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        for (int i = 0; i < n; ++i) {
            cin >> c[i];
        }
        memset(dp, 0, sizeof(dp));

        int ans = 0;
        dp[0] = 1; //初始值 0 一直都是被計算出來的值，也不需要計算
        for (int i = 0; i < n; ++i) {
            memset(sum, 0, sizeof(sum)); //sum 是記錄推導出 j 時該數用過多少次
            for (int j = a[i]; j <= m; ++j) {
                if (dp[j] == 0 && dp[j - a[i]] && sum[j - a[i]] < c[i]) { // j 沒有被計算過，并且它可以通過前面的某一個值加上 a[i] 得到，且 a[i] 沒有用完
                    dp[j] = 1;
                    sum[j] = sum[j - a[i]] + 1;
                    ans++;
                }
            }
        }
        cout << ans << endl;
    }

    return 0;
}