在这里直接展示代码了
C++ 代码
#include<iostream>
using namespace std;
const int N = 110000;
int n, m;
int vv[N], ww[N];
int f[N];
int main()
{
cin >> n >> m;
int num = 1;//作为计时器
for (int i = 1; i <= n; i++)
{
int v, w, s;
cin >> v >> w >> s;//输入重量、价值、剩余数量
for (int j = 1; j <= s; j <<= 1)
{
vv[num] = j * v;//分组后表示重量
ww[num++] = j * w;//表示分组后的价值
s -= j;//求得的数量要减掉
}
if (s)//如果还有剩余的价值,剩余的作为一个分组
{
vv[num] = s * v;//
ww[num++] = s * w;
}
}
//接下来我们就转化为01背包进行计算
//for (int i = 1; i <= n; i++)注意这个是错误的,因为不在是到n了,因为n已经进行分组成num了,我们只能分成num来自进行计算,而且num还算多了,我们要小于num
for(int i=1;i<num;i++)
for (int j = m; j >= vv[i]; j--)
{
f[j] = max(f[j], f[j - vv[i]] + ww[i]);
}
cout << f[m] << endl;
return 0;
}