【Week11作业-E - 选做题11-1】东东与 ATM POJ - 1276

算法

多重背包

题目描述

给出背包容量，以及数种物品，每种物品有数个；

解题思路

相比于0-1背包，多重背包每种物品有多个，直接拆解为0-1背包则物品过多；
相比于完全背包，多重背包每个物品个数有限制，无法直接倒着计算；
我们可以将每种物品根据其数量拆分为相应二进制，如13可拆成1+2+4+6；而1、2、4、6可组合出1-13中任意数量；故而因此转化为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;
}

题目总结

求解多重背包应将每种物品根据个数按二进制拆解，转化为0-1背包。