Part1 01背包
每种物品只有一个，只能选或不选
表示
u[i][j] 表示容量为j时，前i个物品总价值的最大值，u[i][j]即为答案
v[i] 表示第i个物品的价值
w[i] 表示第i个物品的体积
初始化
当容量为0时，价值总和为0，即
u[i][0] = 0;
当选择0个物品时，价值总和为0，即
u[0][j] = 0;
递归式
\[u[i][j] = max(u[i-1][j], u[i-1][j-w[i]] + v[i]); \]当选择第 \(i\) 个物品时，应在第 \(i-1\) 个物品的基础上加上第 \(i\) 个物品的价值，容量应满足 \(j-w[i] > 0\)
当不选择第 \(i\) 个物品时，总价值即为第 \(i-1\) 个物品的总价值
当 \(j-w[i] < 0\) 时，背包容量不足，不能选择第 \(i\) 个物品
例题
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, m;
int u[N][N], v[N], w[N];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d%d", &w[i], &v[i]);
for (int i = 1; i <= n; i++) {
for (int j = m; j >= 1; j--) {
if (j < w[i]) u[i][j] = u[i-1][j];
else u[i][j] = max(u[i-1][j], u[i-1][j-w[i]] + v[i]);
}
}
printf("%d", u[n][m]);
return 0;
}
Part1.2 01背包 - 滚动数组优化
由递推式不难发现，\(i\) 可以省略，即转化为一维数组，\(j\) 的取值简化为 \(m - w[i]\)
递推式
u[j] = max(u[j], u[j-w[i]] + v[i]);
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, m;
int u[N], v[N], w[N];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d%d", &w[i], &v[i]);
for (int i = 1; i <= n; i++) {
for (int j = m; j >= w[i]; j--) {
u[j] = max(u[j], u[j-w[i]] + v[i]);
}
}
printf("%d", u[m]);
}
Part2 完全背包
每种物品有无限个
表示
u[i][j] 表示容量为j时，前i个物品总价值的最大值，u[i][j]即为答案
v[i] 表示第i个物品的价值
w[i] 表示第i个物品的体积
初始化
当容量为0时，价值总和为0，即
u[i][0] = 0;
当选择0个物品时，价值总和为0，即
u[0][j] = 0;
递归式
\[u[i][j] = max(u[i-1][j], u[i-1][j-k*w[i]] + k * v[i]); \]当选 \(0\) 个第 \(i\) 种物品时，价值为 \(u[i][j] = u[i-1][j];\)
当选 \(1\) 个第 \(i\) 种物品时，价值为 \(u[i][j] = u[i-1][j-w[i]] + v[i];\)
当选 \(2\) 个第 \(i\) 种物品时，价值为 \(u[i][j] = u[i-1][j-2 * w[i]] + 2 * v[i];\)
当选 \(k\) 个第 \(i\) 种物品时，价值为 \(u[i][j] = u[i-1][j-k * w[i]] + k * v[i];\)
\((\) \(0\) \(\leq\) \(k\) \(\leq\) \(\lfloor\) \(\frac {j}{w[i]}\) \(\rfloor\) \()\)
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, m, u[N][N], w[N], v[N];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d%d", &w[i], &v[i]);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int t = j / w[i];
for (int k = 0; k <= t; k++) {
u[i][j] = max(u[i][j], u[i-1][j-k*w[i]] + k * v[i]);
}
}
}
printf("%d", u[n][m]);
return 0;
}
Part2.2 滚动数组优化
即
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, m;
int u[N], v[N], w[N];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
for (int j = w[i]; j <= m; j++) {
u[j] = max(u[j], u[j-w[i]] + v[i]);
}
}
printf("%d", u[m]);
return 0;
}
Part3 多重背包
表示
u[i][j] 表示容量为j时，前i个物品总价值的最大值，u[i][j]即为答案
v[i] 表示第i个物品的价值
w[i] 表示第i个物品的体积
s[i] 表示第i个物品的数量
初始化
当容量为0时，价值总和为0，即
u[i][0] = 0;
当选择0个物品时，价值总和为0，即
u[0][j] = 0;
递推式
由完全背包解法可得，选择物品个数为 $t = $ \(\lfloor\) \(\frac {j}{w[i]}\) \(\rfloor\)
由01背包解法可得，选择物品个数为 $t = $ \(min\) \((\) $1, $ \(\lfloor\) \(\frac {j}{w[i]}\) \(\rfloor\) \()\)
所以多重背包递推式为
Code
对于完全背包解法进行些许修改即可
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, m;
int u[N][N], v[N], w[N], s[N];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d%d%d", &w[i], &v[i], &s[i]);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int t = min(s[i], j/w[i]);
for (int k = 0; k <= t; k++) {
u[i][j] = max(u[i][j], u[i-1][j-k*w[i]] + k * v[i]);
}
}
}
printf("%d", u[n][m]);
return 0;
}