JZTXT

背包问题

发布时间 2023-05-24 18:40:43作者: Gery_8002

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\) 个物品

例题

Acwing 2. 01背包问题

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 多重背包

Acwing 4. 多重背包问题 I

表示

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\) \()\)
所以多重背包递推式为

\[u[i][j] = min(s[i], j/w[i]); \]

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;
}