完全背包问题

与01背包的区别:

01背包中每件物品只能拿一次,而完全背包中的物品可以拿无限次。

代码上的区别

前者的二层循环是逆序,而后者则是顺序

顺序

朴素解法,暴力三重循环:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>

using namespace std;
//朴素暴力版本,三重循环

const int N = 1010;
int dp[N][N];
int w[N];
int v[N];

int main() {
int n, weight;
scanf("%d%d", &n, &weight);

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 <= weight; j++)
for (int k = 1; k * w[j] <= j; k++)
dp[i][j] = max(dp[i][j], dp[i - 1][j - k * w[j]] + k * v[j]);
printf("%d\n", dp[n][weight]);
}

优化解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>

using namespace std;

const int N = 10000;
int v[N]; // 体积
int w[N]; // 价值
int f[N][N]; // f[i][j], j体积下前i个物品的最大价值

int main() {
int n, m; // 背包体积
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d%d", &v[i], &w[i]);
f[0][0] = 0;
for (int i = 1; i <= n; i++)
for (int j = 0; j <= m; j++) {
f[i][j] = f[i - 1][j]; // 不选第i个物品
if (j >= v[i]) // 可以选择第i个物品,状态方程见上面推导
f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
}
printf("%d\n", f[n][m]);
return 0;
}

完全背包问题
http://example.com/2022/07/09/完全背包问题/
作者
Charry
发布于
2022年7月9日
许可协议