Coins （POJ 1742）（多重背包QAQ）

Coins （POJ 1742）

【Time Limit: 3000MS Memory Limit: 30000K】

题意：n种货币，每种货币两个属性：a[ i ] (价值)，c[ i ] (数量)；商品价值上限m。问有多少种价格的商品可以不找零买到。

题解：这是一个多重背包的问题，可能会想到用二进制优化，但是算一下时间复杂度是过大了的，实际也会T。所以我们用另外一种方式来做：

dp[ i ]用来表示 i 价值的商品是否可以不找零买到，可以->1，不可以->0

num[ i ]用来表示 i 价值的商品要用到几个当前的这种coin（为了保证用的coin数量不超过上限）

• 【剪枝】：这里做一个优化，有人叫“剪枝”：就是c[ i ]=min(c[ i ],m / a[ i ])。因为如果a[ i ] * c[ i ]>m，那么多余的coin数量是没有用的，所以说c[i]最大就用到m / a[ i ]。
• 【num[ ]的更新】我们的num[ ]初始化都为0，代表该价值下还没有用第 i 种coin；如果dp[ j ]=1的话，说明前面跑过的coin已经组成过 j 价值了，所以这时候我们只用0个第 i 个coin即可，那我们就不需要处理num[ j ]；如果dp[ j ]=0，那么num[ j ]=num[ j - a[ i ] ]+1，这儿很好理解了就。

• 【num[ ]更新举例】假设a[ 1 ]=4，a[ 2 ]=6，现在先不考虑数量

  可组成的价值，括号里是用的a[ i ]的个数

a[1] :               a[2] :       
      4(1)                 6(1)
      8(2)                10(1)
     12(3)                12(0)
     16(4)                14(1)
     20(5)                18(1)
     24(6)                22(1)
     28(7)                24(0)
           

可以发现：

dp[ j ]=0->    num[ j ]=num[ j-a[ i ] ]+1
dp[ j ]=1->    num[ j ]=num[ j ]
           

• 再就是注意num[ ]数组的初始化，每一种coin都要初始化一次

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <list>
#include <map>
#define P(x) x>0?x:0
#define INF 0x3f3f3f3f

using namespace std;
typedef long long ll;
typedef vector<int>:: iterator VITer;
const int maxn=105;
const int maxc=1e5+5;

int a[maxn];
int c[maxn];
int dp[maxc];//dp[i]是i价值的状态是否存在，存在为1，不存在为0
int num[maxc];//num[i]:该种coin可以组成的价值i，用掉了几个这种coin
int n,m,ans;//n是coins的种类，m是价值的上限

void init()
{
    memset(dp,0, sizeof(dp));
    memset(num,0, sizeof(num));
    dp[0]=1;//价值为0这种状态是存在的，赋值为1
    ans=0;
}

int main()
{
    while(~scanf("%d%d",&n,&m)&&(n||m))
    {
        init();
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
            scanf("%d",&c[i]);
        for(int i=1;i<=n;i++)//coin的种类
        {
            //这里做一个优化，有人叫“剪枝”：就是c[i]=min(c[i],m/a[i])
            // 因为如果a[i]*c[i]>m，那么多余的coin数量是没有用的，所以说c[i]最大就用到m/a[i]
            c[i]=min(c[i],m/a[i]);
            for(int j=a[i];j<=m;j++)
            {
                if(dp[j-a[i]] && !dp[j] && (num[j]=(num[j-a[i]]+1)) <= c[i])
                {
                        dp[j]=1;
                }
            }
            memset(num,0, sizeof(num));//因为是对于每一种coin来说所用的数量
        }
        for(int i=1;i<=m;i++)
        {
            if(dp[i])
                ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}