分析
看了一眼数据范围,$1000 \times 2000 \times 2000$,直接暴力三重循环肯定超时了。
提示中显示,可以使用二进制优化的方法,也就是使用二进制对背包进行压缩。
我们直接把所有物品都变成一个一个的肯定不行,我们可以利用二进制独特的压缩方式,可以把多个物品压缩成一个物品,这样物品的数量压缩的范围简化到$1000 \times log(2000)$,时间复杂度近似于 $1000 \times 11 \times 2000$,我们看这是可以在$1S$中跑完的,时间复杂度可以通过了。
#include <iostream>
#include <vector>
using namespace std;
const int N = 2010;
int n,m;
int dp[N];
//存放压缩后物品的仓库
typedef struct Good
{
int v,w;
}Good;
int main()
{
cin>>n>>m;
vector<Good> goods;
for(int i = 1; i <= n; i++)
{
int v,w,s;
cin>>v>>w>>s;
//状态压缩
//10 -> 1 + 2 + 4 + 3
for(int k = 1; k <= s; k *= 2)
{
goods.push_back({v*k, w*k});
s -= k;
}
//不能分解的,单独构成一个物品
if(s) goods.push_back({v*s, w*s});
}
//安装01背包的模板进行遍历
for(int i = 0; i < goods.size(); i++)
for(int j = m; j >= goods[i].v; j--)
dp[j] = max(dp[j], dp[j - goods[i].v] + goods[i].w);
cout<<dp[m]<<endl;
return 0;
}