关键
1.输入考虑好物品下标对应，为了后面打表 2.明白 mΣki ->mΣlog(ki) 也就是二进制分解对时间复杂度 的优化
验证
acwing传送门
板子
代码语言：javascript复制#include<iostream>
using namespace std;
const int MAXN =1100;
int w[MAXN];
int v[MAXN];
int main()
{
int n,m;
cin>>n>>m;
int number =1;//为了打表时候第一个物品下标是1
v[0]=w[0]=0;
while(n--)
{
int weight;
int value;
int k;
cin>>weight>>value>>k;
//二进制拆分
for(int j=1; j<=k; j<<=1)
{
w[number]=j*weight;
v[number]=j*value;
number ;
k-=j;
}
//此时的k很小了，与前面的所有出现过的j求和就是原来的k，并且这个组合 可以表示[0,原来k]数量 这就是二进制分解的妙处，还降低了时间复杂度
if(k)
{
w[number]=k*weight;
v[number]=k*value;
number ;
}
}
int dp[MAXN][110];
// 0-1 背包打表
for(int i=0; i<number; i )//这里0开始，是初始化和状态计算同时进行
{
for(int j=0; j<=m; j )
{
if(i==0||j==0)
{
dp[i][j]=0;
continue;
}
dp[i][j]=dp[i-1][j];
if(j>=w[i])dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]] v[i]);
}
}
cout<<dp[number-1][m]<<endl;
}
