Acwing 7. 混合背包问题
有 \(N\) 种物品和一个容量是 \(V\) 的背包。
物品一共有三类:
- 第一类物品只能用 \(1\) 次(01背包);
- 第二类物品可以用无限次(完全背包);
- 第三类物品最多只能用 \(s_i\) 次(多重背包);
每种体积是 \(v_i\),价值是 \(w_i\)。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。
思路:
根据上文对这三个背包问题的了解,列出他们各自的转移方程
-
01: \(f[i,j] = max(f[i-1][j],f[i - v[i]] + w[i])\)
-
多重: \(f[i,j] = max(f[i - 1][j],f[i - 1,j - v[i]],+,...,f[i - 1,j - S_i v[i]] + S_i w[i])\)
-
完全:\(f[i,j] = max(f[i - 1][j],f[i - 1,j - v[i]],+,...,f[i - 1,j - S v[i]] + S w[i])\)
可知,当前物品的选法,和相应的更新值,和之前的物品类型无关。所以每次判断当前物品的类型,选择对应的转移方程来进行转移就可以了。
通过分析时间复杂度可知,多重背包需要用到二进制优化。
实现:
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N = 1005;
int dp[N], n, m;
struct Good
{
int w, v;
} good[N];
int main()
{
scanf("%d%d", &n, &m);
// 遍历物品
while (n--)
{
int v, w, s;
scanf("%d%d%d", &v, &w, &s);
// 如果可以无数次用,就是完全背包
if (!s)
// 遍历体积
for (int j = v; j <= m; j++)
dp[j] = max(dp[j], dp[j - v] + w);
else
{
// 将01背包看成可以使用1次的多重背包
if (s == -1)
s = 1;
// 二进制优化多重背包看成01背包
int cnt = 1;
for (int i = 1; i <= s; i *= 2)
{
good[cnt].v = v * i;
good[cnt++].w = w * i;
s -= i;
}
// 最后一部分
if (s > 0)
{
good[cnt].v = v * s;
good[cnt++].w = w * s;
}
// 遍历物品
for (int i = 1; i < cnt; i++)
// 遍历体积
for (int j = m; j >= good[i].v; j--)
dp[j] = max(dp[j], dp[j - good[i].v] + good[i].w);
}
}
printf("%d\n", dp[m]);
return 0;
}
标签:good,int,max,混合,背包,物品,dp,Acwing
From: https://www.cnblogs.com/zxr000/p/16999868.html