3 多重背包问题
3.1 题目
有 种物品和一个容量为
的背包。第 i 种物品最多有
件可用，每件耗费的 空间是
，价值是
。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。
3.2 朴素算法
我们可以讲个物品拆分，则得到
个物品。将原问题转化成01背包问题，时间复杂度为
。
状态转移方程为：
3.3 优化
利用二进制思想，讲第种物品分成若干件物品，可以有
，等等。这样
件物品至多拆分成
件物品。
for (int i = 1; i <= n; i++) {
int num = min(p[i], V / w[i]);
for (int k = 1; num > 0; k <<= 1) {
if (k > num) k = num;
num -= k;
for (int j = V; j >= w[i] * k; j--)
f[j] = max(f[j], f[j - w[i] * k] + v[i] * k);
}
}
3.4 例题
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
int a, b, c, cnt;
int dp[100000];
int v[100000];
int w[100000];
int main()
{
scanf("%d%d",&n, &m);
for(int i=1; i<=n; ++i)
{
scanf("%d%d%d",&a,&b,&c);
for(int j=1; j<=c; j<<=1)
{
v[++cnt] = j*a;
w[cnt] = j*b;
c -= j;
}
if(c)
{
v[++cnt] = c*a;
w[cnt] = c*b;
}
}
for(int i=1; i<=cnt; ++i)
{
for(int j=m; j>=w[i]; --j)
{
dp[j] = max(dp[j-w[i]] + v[i], dp[j]);
}
}
cout<<dp[m]<<endl;
return 0;
}
