题解 | #多重背包#

多重背包

每种物品有若干个,物品i的体积：w[i]、价值：v[i]、数量：amount

第i轮：dp[j]:前i个物品装进容量为j的背包所获得的最大价值

采用二进制 将同种物品组合成新的物品，化为0-1背包求解

#include<iostream>
#include<string>
using namespace std;

const int maxn=500010;
int w[maxn];//体积
int v[maxn];//价值

int dp[maxn];

int best(int sum,int n){//0-1背包（优化）
    for(int i=0;i<=sum;i++)dp[i]=0;
    for(int i=1;i<=n;i++){
        for(int j=sum;j>=w[i];j--){
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
    return dp[sum];
}

int main(){
    int sum,n;
    while(scanf("%d%d",&sum,&n)!=EOF){
        int index=1;//物品起始下标
        for(int i=0;i<n;i++){
            int amount,volume,value;
            scanf("%d%d%d",&amount,&volume,&value);
            int j=1;
            while(amount>=j){//相同物品重新组合
                amount=amount-j;
                w[index]=volume*j;
                v[index]=value*j;
                index++;
                j=j*2;//二进制
            }
            if(amount>0){
                w[index]=volume*amount;
                v[index]=value*amount;
                index++;
            }
        }
        printf("%d\n",best(sum,index-1));
    }
}

看到官方给的题解很妙，相当于输入一个就动态递推一次

• 如果当前物品总体积大于背包容量：本次递推为完全背包
• 否则将其按照1,2,4,8...二进制重新组合成新的物品，本次递推为0-1背包

#include<iostream>
using namespace std;

const int maxn=10001;
int w[maxn];//体积
int v[maxn];//价值
int dp[maxn];

int main(){
    int sum,n;
    while(scanf("%d%d",&sum,&n)!=EOF){
        for(int i=0;i<=sum;i++)dp[i]=0;//初始化
        
        for(int i=0;i<n;i++){
            int amount,volume,value;
            scanf("%d%d%d",&amount,&volume,&value);
            
            if(amount*volume>sum){//完全背包
                for(int j=volume;j<=sum;j++){//从前往后
                    dp[j]=max(dp[j],dp[j-volume]+value);
                }
            }
            else{//0-1背包
                int j=1;
                int index=1;//拆分后物品起始下标
                while(amount>=j){//物品拆分
                    amount=amount-j;
                    w[index]=volume*j;
                    v[index]=value*j;
                    index++;
                    j=j*2;//二进制拆分
                }
                if(amount>0){
                    w[index]=volume*amount;
                    v[index]=value*amount;
                    index++;
                }
                for(int i=1;i<index;i++){
                    for(int j=sum;j>=w[i];j--){//从后往前
                        dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
                    }
                }
            }
        }
        printf("%d\n",dp[sum]);
    }
}