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