分析一波
代码如下
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 12010, M = 2010; //n * logm 个包
int n, m;
int f[M];
int w[N], v[N];
int main()
{
scanf("%d%d", &n, &m);
int cnt = 0; //这个是目标数组的下标
for (int i = 1; i <= n; i ++)
{
int a, b, s; //读取进来体积、价值、个数,然后打包存进数组
scanf("%d%d%d", &a, &b, &s);
int k = 1; //打包的物品个数
while (k <= s)
{
cnt ++;
v[cnt] = a * k; //更新打包后的体积和价值
w[cnt] = b * k;
s -= k; //总体积-打好包的体积
k *= 2; //打包数 * 2
}
if (s > 0) //这里是多出来的那个孤儿
{
cnt ++;
v[cnt] = a * s;
w[cnt] = b * s;
}
}
n = cnt; //更新最后的包的个数
//接下来是01背包问题的求解过程了
for (int i = 1; i <= n; i ++)
// for (int j = 0; j <= m; j ++)
// {
// f[i][j] = f[i - 1][j];
// if (j >= v[i])
// f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
// }
for (int j = m; j >= v[i]; j --)
f[j] = max(f[j], f[j - v[i]] + w[i]);
printf("%d\n", f[m]);
return 0;
}
欸嘿!01背包不用一维优化的写法会 $\huge\color{red}{\textit{MLE}}$, 就是内存溢出,不行你试试。
总结
我觉得比较难想通的是求二进制阶乘的那一块,后面就是01背包的板子。