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;
}