算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
// 思路:多重背包的优化算法,将物品数量使用1,2,4...等箱子分组存放,转化为01背包问题,此时的物品总数变为箱子的总数
#include <iostream>
using namespace std;
const int N = 12010, M = 2010;
int n, m, f[M];
int v[N], w[N];
int main()
{
scanf("%d%d", &n, &m);
int cnt = 0; // cnt从1开始计数
for (int i = 1; i <= n; i ++ )
{
int a, b, s;
scanf("%d%d%d", &a, &b, &s);
// k表示当前箱子的大小
int k = 1;
// 1,2,4...从小到大每个箱子一定要装,并且箱子一定要装满,所有有可能会由剩余的物品没装
while (k <= s) // 当剩余的物品数大于箱子大小时可以分装
{
cnt ++ ; // 加一个箱子
v[cnt] = a * k; // 当前箱子的容积
w[cnt] = b * k; // 当前箱子的价值
s -= k;
k *= 2;
}
// 将剩余的物品另外装一个箱子
if (s > 0)
{
cnt ++ ;
v[cnt] = a * s;
w[cnt] = b * s;
}
}
// 此时的物品总数变为箱子的总数
n = cnt;
for (int i = 1; i <= n; 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;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla