当前位置 博文首页 > 广大菜鸟的博客：背包问题算法模板（待完善其他背包）
01背包： 有N 个物品和一个容量为V的背包，每种物品都有1件可用，第i种物品的费用是c[i]，价值是w[i]，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？
完全背包：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
多重背包：有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
比较这两个题目以及上次谈到的0-1背包，会发现不同点在于每种背包的数量，01背包是每种只有一件，完全背包是每种无限件，而多重背包是每种有限件。
n代表种类数量，m代表背包容量限制
状态转移方程：f(i,j) = max(f(i,j),f(i-1,j-ui)+wi)
// 一维数组解法
#include<iostream>
#define MAX_M 12880 //最大限重
#define MAX_N 3402 // 最大种类数
using namespace std;
int dp[MAX_M + 1];
int weights[MAX_N + 1];
int values[MAX_N + 1];
int main() {
int n, m, i, j;
cin >> n >> m;
for (i = 1; i <= n; i++) {
cin >> weights[i] >> values[i];
}
for (int i = 1; i <= n; i++) {
for (int j = m; j >= weights[i]; j--) { //逆序
dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
}
}
cout << dp[m] << endl;
}
具体案例：01背包问题的解决
转移方程：f(i,j) = max( f(i,j),f(i,j-ui)+wi)
// 一维数组解法
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1100;
int f[N], v[N], w[N];
int main() {
int n, m, i, j, k;
cin >> n >> m;
for (i = 1; i <= n; i++) cin >> v[i] >> w[i]; // 体积和价值
for (i = 1; i <= n; i++) // 物品类数
for (j = v[i]; j <= m; j++) { // 容积，正序
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
cout << f[m];
return 0;
}
具体案例：完全背包的解决
转移方程：f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
#include<stdio.h>
#include<algorithm>
const int N = 200;
// 动态空间 体积 价值 原来系统物品数量
int f[N], v[N], w[N], s[N];
int main() {
int n, m;
//cin >> n >> m;
scanf_s("%d%d", &n, &m);
for (int i = 1; i <= n; i++) //cin >> v[i] >> w[i] >> s[i];
scanf_s("%d%d%d", &v[i], &w[i], &s[i]);
for (int i = 1; i <= n; i++) { // 前i类
for (int j = m; j >= v[i]; j--) { //容积，逆序
for (int k = 0; k * v[i] <= j && k <= s[i]; k++) { //数量
f[j] = max(f[j], f[j - k * v[i]] + k * w[i]);
}
}
}
printf("%d\n", f[m]);
return 0;
}
推荐博客：https://blog.csdn.net/m0_37809890/article/details/83153974
推荐视频：
https://www.bilibili.com/video/BV1qt411Z7nE/?spm_id_from=333.788.videocard.0
