#Z114524. 理包 题解

首先我们看到这一个题，先分析一下题意：亮亮学长堵完桥后想理包，他有一项技术可以将每个物品压缩成$1*n_i$的形状，而他的背包有$m$格空间，背包也是$1*m$的格式。每个物品有数量$num_i$，体积$v_i$，价值$a_i$。

这个时候我们能想到用背包去解决这个问题，但是一些蒟蒻只会01背包，不知道数量变多了该怎么办。

这个时候我们不妨将多个物品当成多种物品去看，他们的价值，体积一模一样，可以把他们看成一群克隆体。这个时候我们只需要在嵌套一层循环，来表示每个物品有多少个克隆物品就可以解决这个问题了。

那么恭喜你解决了多重背包难题。代码如下：

#include<bits/stdc++.h>
using namespace std;
long long dp[20001000];
long long a[11000],v[11000],num[11000];
int main(){
	long long n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>num[i]>>v[i]>>a[i];
	}
	for(int i=1;i<=n;i++){
		for(int x=1;x<=m[i];x++){
			for(int j=t;j>=0;j--){
				if(j>=b[i]){
					dp[j]=max(dp[j],dp[j-b[i]]+a[i]);
				}
			}
		}
	}
	cout<<dp[t];
}

这个时候同学们应该会发现自己并没有AC，100分但是有一个点TLE了，这个是亮亮学长留下的彩蛋点，分值高达一分。这个时候再来看我们的代码，时间复杂度太高了，达到了$O(m\sum_{i = 1}^{n} num _i)$。看一眼数据范围，测试点11（彩蛋点）的数据，$\sum_{i = 1}^{n} num _i\le10^5,m=3*10^3$,如果按我们刚才的那种朴素算法去做的话，TLE是必然的，那么有没有更快也能通过的算法呢？有的兄弟，有的！

它就是二进制优化，首先我们要明白一件事，所有正整数都可以进行二进制拆分，即所有数都可以拆成多个$2^n$的和。但是我们一定要从$2^0$开始拆，因为我们要确保它能表示$1$~$num_i$所有数且拆成的每个数只有一个。举个例子：10。$10=2^0+2^1+2^2+3$。大家可以试试后面这4个数可以组成1~10之间的所有数。

这就是二进制优化的原理。由于可以表示所有数且拆成的每个数只有一个。我们就可以把原先1种物品，$num_i$个数量，优化成$log_2num_i$种物品，1个数量。时间复杂度降到了$O(m\sum_{i = 1}^{n} log_2num _i)$，跑得快的不是一星半点。当然当拆分物品时不要忘了更新新物品的价值，体积。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,m,ans,cnt=1;
long long f[1000005];//其实就是DP数组
long long w[1000005],v[1000005];
int main()
{
    long long a,b,c;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%lld%lld%lld",&c,&b,&a);
        for(int j=1;j<=c;j<<=1)
        {
            v[++cnt]=j*a,w[cnt]=j*b;//更新价值，体积
            c-=j;
        }
        if(c)v[++cnt]=a*c,w[cnt]=b*c;//如果拆分后还有剩余，作为另一种物品。
    }//二进制优化
    for(int i=1;i<=cnt;++i){
        for(int j=m;j>=w[i];--j){
            f[j]=max(f[j],f[j-w[i]]+v[i]);
        }
    }//混合背包
    printf("%lld\n",f[m]);
    return 0;
}