题解：B2173 多重背包

· · 题解

B2173 多重背包

解析

本题为多重背包模版题。

首先可以想到用动态规划，设 dp_i 表示背包内物品总体积为 i 时的最大总价值。设一个物品体积为 a，价值为 b，那么可以得出

dp_i=\max(dp_i,dp_{i-a}+b)

注意要保证 i\ge a！

但是本题中物品不只有一个，因此我们可以把它们拆成多个单一物品，存在数组中再进行动态规划。但这么做会超时！

这时我们可以用二进制拆分物品数量，将拆分后的物品依次组合成新的一件，随后再进行存储并进行动态规划。举个例子，设某件物品数量为 3，那么可以分为 1 和 2；数量为 10，那么可以分为 1、2、4 和 3。

注意拆分时，剩下的部分也要存进去！

代码

#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
int t,m,dp[100005];
int n=1;
pair<int,int>a[100005];
int main(){
    scanf("%d%d",&m,&t);
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&y,&z,&x);
        for(int j=0;j<=40;j++){
            int k=(1<<j);
            if(k<=x){//可以就拆
                x-=k;
                a[n].f=y*k,a[n].s=z*k;//别忘记乘
                ++n;
            }else break;
        }
        if(x){//注意剩余部分
            a[n].f=y*x,a[n].s=z*x;
            ++n;
        }
    }
    for(int i=1;i<=n;i++){//普通背包
        for(int j=t;j>=a[i].f;j--){
            dp[j]=max(dp[j],dp[j-a[i].f]+a[i].s);
        }
    }printf("%d",dp[t]);
    return 0;
}