算法

多重背包

題目描述

給出背包容量，以及數(shù)種物品，每種物品有數(shù)個；

解題思路

相比于0-1背包，多重背包每種物品有多個，直接拆解為0-1背包則物品過多；
相比于完全背包，多重背包每個物品個數(shù)有限制，無法直接倒著計算；
我們可以將每種物品根據(jù)其數(shù)量拆分為相應(yīng)二進(jìn)制，如13可拆成1+2+4+6；而1、2、4、6可組合出1-13中任意數(shù)量；故而因此轉(zhuǎn)化為0-1背包問題。

代碼

#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 100010;
int f[maxn];
int a[maxn];
int main(){
    int sum,n;
    while(cin>>sum>>n){
        memset(f,0,sizeof(f));
        int x,k;
        int cnt=0;
        for(int i=1;i<=n;i++){
            cin>>k>>x;
            int temp=1;
            while(temp<=k){
                a[++cnt]=temp*x;
                k-=temp;
                temp*=2;
            }
            if(k!=0){
                a[++cnt]=k*x;
            }
        }
        for(int i=1;i<=cnt;i++)
            for(int j=sum;j>=a[i];j--){
                f[j]=max(f[j-a[i]]+a[i],f[j]);
            }
        cout<<f[sum]<<endl;
    }
    return 0;
}

題目總結(jié)

求解多重背包應(yīng)將每種物品根據(jù)個數(shù)按二進(jìn)制拆解，轉(zhuǎn)化為0-1背包。