hdu2844"Coins"多重背包

一些感受（廢話）

看了一下，可以将多重背包轉化為0/1背包，将某種多個的硬币，對每一個硬币，每一個dp狀态都有選擇/不選擇的0/1方案，由于硬币數可能很多，網上有部落客使用二進制優化方案。這種方案是我第一次接觸。以後需要學習一下。

連結：二進制優化，轉化為0/1背包解決的方案

我的思路

一開始，我想要定義一個數組st[n][m]，表示dp[m]狀态硬币A[n]對應的數量，狀态進行轉移時，前狀态必須有對應硬币剩餘才可以進行轉移（狀态轉移的硬币數量限制），但因為1<=n<=100, 1<=m<=100000，送出的時候運作記憶體超限。

但後來發現！！！在狀态轉移算法中，周遊每種硬币進行轉移的時候每次隻需要操作一種硬币，是以隻需要在狀态轉移算法中定義一個一維臨時數組temp[m]存儲對應狀态的硬币數量。記憶體一下子減少了很多。

#include<iostream>
using namespace std;
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
const int maxn = 101;
const int maxm = 1e5+1;//100001
bool dp[maxm]; //dp[m]==true：表示金額為m可以用硬币組合出來
int A[maxn]; //A[i]:對應硬币的面值
int C[maxn]; //C[i]:對應硬币的數量

int m, n;

void init()
{
    memset(dp, false, sizeof(dp));
    dp[0] = true;
}

int solve()//狀态轉移算法：遞推dp,傳回結果
{
    int temp[maxm];//temp[c]:dp[c]狀态對應某一硬币的剩餘硬币數，臨時變量
    for(int i = 1; i <= n; i++){//硬币次元
        for(int c = 0; c <= m; c++){//初始化所有背包狀态的硬币數量
            temp[c] = C[i];
        }
        for(int c = A[i]; c <= m; c++){
            if(!dp[c] && dp[c-A[i]] && temp[c-A[i]] > 0){//目前狀态沒有出現過可行組合&&對應前一個狀态可行且硬币剩餘不為0
                dp[c] = true;//能組合出目前狀态
                temp[c] = temp[c-A[i]] - 1;//硬币數是前一個狀态減去1
            }
        }
    }

    int ans = 0;
    for(int c = 1; c <= m; c++){
        if(dp[c]){
            ans++;
        }
    }
    return ans;
}

int main()
{
    //freopen("in.txt", "r", stdin);
    while(~scanf("%d %d", &n, &m) &&n&&m){//每一個案例
        for(int i = 1; i <= n; i++)//輸入硬币的面值
            scanf("%d", &A[i]);

        for(int i = 1; i <= n; i++)//輸入硬币的數量
            scanf("%d", &C[i]);

        init();//初始化dp數組

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

    return 0;
}