题目链接：https://www.acwing.com/problem/content/5/

最近没有比赛可打，好好看看基础。

多重背包的朴素写法很简单，基本上都能写，复杂度nmk级别的，在数据量几千的情况下就处理不了了。

因此我们考虑用空间换时间，对物品进行二进制优化，“将物品变得多多的”，例如7 ，我们可以看成 1 2 4  ，也就是1倍价值1倍重量看做一个物品，2倍价值2倍重量看做一个物品，4倍价值4倍重量看做一个物品...依次类推，这样一个物品就被划分成了 logk  件物品。这里面的具体操作是一个累减的过程。

这样在空间上就增加了，因此我们再用01背包的时候有必要对其进行空间优化，优化成一维的dp。

code：

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
const int nn = 2010;
int n,m;
int v,w,s;
struct wupin{
	int v,w;
};
vector<wupin> ve;
int f[nn]; 
int main()
{
	cin>>n>>m;
	while(n--){
		cin>>v>>w>>s;
		ve.push_back({0,0});
		for(int i=1;i<=s;i*=2){
			s-=i;
			ve.push_back({v*i,w*i});
		}
		if(s>0) ve.push_back({v*s,w*s});
	}
	/*for(int i=1;i<ve.size();i++){
		for(int j=0;j<=m;j++){
			if(j>=ve[i].v) f[i][j] = max(f[i-1][j],f[i-1][j-ve[i].v]+ve[i].w);
			else f[i][j] = f[i-1][j];
		} 
	}*/
	for(auto it:ve)
	for(int i=m;i>=1;i--){
		if(i>=it.v)
			f[i] = max(f[i-it.v]+it.w,f[i]);
	}
	cout<<f[m]<<endl;
}