AKSZ-背包
2024-06-30 19:11:31
发布于:广东
C++ 中的 背包和背包问题。这两个问题都是经典的动态规划问题,涉及到如何在给定背包容量和物品重量、价值的情况下,选择最优的物品放入背包以获得最大的总价值。
问题描述
是一个经典的动态规划问题,指的是有 n 个物品和一个容量为 W 的背包,每个物品只能选择装入一次或不装入。目标是在不超过背包容量的前提下,选择物品使得背包中物品的总价值最大。
解法思路
- 定义数组元素含义: 我们定义一个二维数组
dp[i][j]
,表示在前 i 个物品中任取物品,放进容量为 j 的背包中,背包所能装的最大价值。 - 递推关系式: 对于每个物品 i,有两种选择:放入背包或不放入背包。因此递推公式如下:
- 不放第 i 个物品:
dp[i][j] = dp[i-1][j]
- 放第 i 个物品:
dp[i][j] = dp[i-1][j-w[i]] + v[i]
- 最终结果:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
- 不放第 i 个物品:
- 初始化: 初始化第一行和第一列为 0。
- 填表格: 根据递推公式填充整个二维数组。
- 求解最终结果: 最终结果为
dp[n][W]
,其中 n 是物品数量,W 是背包容量。
代码实现
以下是 C++ 中 的代码示例:
const int MAX_N = 1005; // 最大物品数量
const int MAX_W = 1005; // 最大背包容量
int w[MAX_N]; // 物品重量
int v[MAX_N]; // 物品价值
int dp[MAX_N][MAX_W]; // dp 数组
int knapsack(int n, int W) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= W; ++j) {
if (j >= w[i]) {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
} else {
dp[i][j] = dp[i-1][j];
}
}
}
return dp[n][W];
}
问题描述
完全背包问题与 类似,但不同之处在于每种物品的数量是的。也就是说,每个物品可以选择装入多次。
解法思路
- 定义数组元素含义: 我们仍然定义一个一维数组
dp[j]
,表示在前 i 个物品中任取物品,放进容量为j
的背包中,背包所能装的最大价值。 - 递推关系式: 对于每个物品
i
,有两种选择:放入背包或不放入背包。因此递推公式如下:- 不放第 i 个物品:
dp[j] = dp[j]
- 放第 i 个物品:
dp[j] = max(dp[j], dp[j-w[i]] + v[i])
- 不放第 i 个物品:
- 初始化: 初始化一维数组
dp[j]
为 0。 - 填表格: 从前向后遍历背包容量,根据递推公式更新
dp[j]
。 - 求解最终结果: 最终结果为
dp[W]
,其中W
是背包容量。
代码实现
以下是 C++ 中的代码示例:
const int MAX_N = 1005; // 最大物品数量
const int MAX_W = 1005; // 最大背包容量
int w[MAX_N]; // 物品重量
int v[MAX_N]; // 物品价值
int dp[MAX_W]; // dp 数组
int knapsack(int n, int W) {
for (int i = 1; i <= n; ++i) {
for (int j = w[i]; j <= W; ++j) {
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
}
}
return dp[W];
}
这段代码中,我们使用了一维数组 dp[j]
来记录背包容量为 j
时的最大价值。通过遍历物品和背包容量,不断更新 dp[j]
的值,最终得到的最优解。
这里空空如也
有帮助,赞一个