前置知识:
01背包问题:动态规划之01背包模型_如何何何的博客-CSDN博客
完全背包问题:动态规划之完全背包模型_如何何何的博客-CSDN博客
多重背包问题:
给定一个有一定容量的背包,和 n 个物品,每个物品有 si 件;
每个物品有其对应的体积和价值;
问背包最多能装下的物品的最大价值为多少。
输入格式:
第一行两个整数,N,V,分别表示物品数量和背包容积;
接下来有 N 行,每行两个整数 vi,wi 用空格隔开,分别表示第 i 件物品的体积和价值。
输出格式:
输出一个整数,表示最大价值。
思路:
每件物品的数量是有限的,并且各不相同。并不能和完全背包问题一样优化;
如果数据范围比较小,可在01背包的基础上加上第三重循环(枚举选几件该物品);
故可以将01背包当做特殊的多重背包来处理。
代码模板如下:
//一维
#include<iostream>
using namespace std;
const int N = 110;
int f[N][N];
int n, m;//n件物品,容量是m
int main() {
cin >> n >> m;
int v, w, s;
for (int i = 1; i <= n; i++) {
cin >> v >> w >> s;
for (int j = 0; j <= m; j++) {
f[i][j] = f[i - 1][j];//不选
for (int k = 0; k <= s; k++)//选k件
if (k * v <= j)f[i][j] = max(f[i][j], f[i - 1][j - k * v] + k * w);
}
}
cout << f[n][m];
return 0;
}
//一维
#include<iostream>
using namespace std;
const int N = 110;
int f[N];
int n, m;//n件物品,容量是m
int main() {
cin >> n >> m;
int v, w, s;
for (int i = 1; i <= n; i++) {
cin >> v >> w >> s;
for (int j = m; j >= v; j--) {
for (int k = 0; k <= s; k++)//选k件
if (k * v <= j)f[j] = max(f[j], f[j - k * v] + k * w);
}
}
cout << f[m];
return 0;
}
二进制优化:
将每一类物品打包成2^0、2^1、2^2 …… 这样的logn堆物品;
将这些物品进行组合就可以组合出1~n内的任何数量的该物品;
即将所有分好的物品堆进行01背包处理就可以枚举出所有情况。
代码模板如下:
#include<iostream>
using namespace std;
const int N = 2010;
int f[N];
int w[N * N], v[N * N], cnt = 0;//最多1000*logn堆物品
int n, V;
int main() {
cin >> n >> V;
int v1, w1, s;
for (int i = 0; i < n; i++) {//打包
cin >> v1 >> w1 >> s;
int k = 1;
while (s) {
if (s >= k) {
v[cnt] = k * v1;
w[cnt++] = k * w1;
s -= k;
}
else {
v[cnt] = s * v1;
w[cnt++] = s * w1;
s = 0;
}
k *= 2;
}
}
for (int i = 0; i <= cnt; i++)//01背包
for (int j = V; j >= v[i]; j--)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[V];
return 0;
}
例题1 . 庆功会:
信息学奥赛一本通T1269-庆功会 - C语言网 (dotcpp.com)文章来源:https://www.toymoban.com/news/detail-472742.html
多重背包裸题,默写多重背包模板即可。文章来源地址https://www.toymoban.com/news/detail-472742.html
AC代码如下:
#include<iostream>
using namespace std;
const int N = 6010;
int v[N], w[N], cnt = 0;
int f[N];
int n, V;
int main() {
cin >> n >> V;
int v1, w1, s;
for (int i = 0; i < n; i++) {
cin >> v1 >> w1 >> s;
int k = 1;
while (s) {
if (s >= k) {
v[cnt] = k * v1;
w[cnt++] = k * w1;
s -= k;
}
else {
v[cnt] = s * v1;
w[cnt++] = s * w1;
s = 0;
}
k *= 2;
}
}
for (int i = 0; i < cnt; i++)
for (int j = V; j >= v[i]; j--)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[V];
return 0;
}
到了这里,关于动态规划之多重背包模型的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!