完全背包问题动态规划（完全背包问题例题）

完全背包问题动态规划

简介

完全背包问题是一种动态规划问题，其中允许背包中的物品重复。与 0-1 背包问题不同，其中每个物品只能选择一次，完全背包问题允许使用任意数量的同一物品。

问题描述

给定一个背包容量为 W，以及 n 件物品，每件物品有其重量 wi 和价值 vi。目标是在不超过背包容量的情况下，选择物品装入背包，以获得最大总价值。

动态规划解法

完全背包问题的动态规划解法使用一个二维数组 dp[n+1][W+1]，其中：

dp[i][j] 表示在考虑前 i 件物品后，背包容量为 j 时，能获得的最大价值。

动态规划方程

对于每一件物品 i，我们有两种选择：1.

选择物品 i

：如果背包容量足够容纳物品 i，则选择物品 i 会增加价值 vi，但背包容量减少 wi。因此：```dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi] + vi)```2.

不选择物品 i

：如果不选择物品 i，则背包容量和价值保持与前一步相同：```dp[i][j] = dp[i-1][j]```

初始化

dp[0][0] = 0，因为没有物品时，背包价值为 0。

对于所有 j：dp[0][j] = 0，因为没有物品时，任何容量的背包价值都为 0。

对于所有 i：dp[i][0] = 0，因为容量为 0 时，任何物品都无法放入。

计算顺序

我们从 i = 1 开始，逐个考虑每件物品，并从 j = 1 开始，逐个考虑每种容量。

时间复杂度

该解法的时间复杂度为 O(nW)，其中 n 是物品数量，W 是背包容量。

空间复杂度

该解法需要 O(nW) 的空间来存储 dp 数组。

示例

考虑一个背包容量为 5，有 3 件物品的完全背包问题：| 物品 | 重量 (wi) | 价值 (vi) | |---|---|---| | 1 | 1 | 1 | | 2 | 2 | 6 | | 3 | 3 | 10 |

动态规划表

| 容量 \ 物品 | 0 | 1 | 2 | 3 | 4 | 5 | |---|---|---|---|---|---|---| | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 1 | 0 | 1 | 1 | 1 | 1 | 1 | | 2 | 0 | 1 | 6 | 6 | 6 | 6 | | 3 | 0 | 1 | 6 | 10 | 10 | 10 |

最终答案

：最大价值为 10，可通过选择物品 3 一次。

**完全背包问题动态规划****简介**完全背包问题是一种动态规划问题，其中允许背包中的物品重复。与 0-1 背包问题不同，其中每个物品只能选择一次，完全背包问题允许使用任意数量的同一物品。**问题描述**给定一个背包容量为 W，以及 n 件物品，每件物品有其重量 wi 和价值 vi。目标是在不超过背包容量的情况下，选择物品装入背包，以获得最大总价值。**动态规划解法**完全背包问题的动态规划解法使用一个二维数组 dp[n+1][W+1]，其中：* dp[i][j] 表示在考虑前 i 件物品后，背包容量为 j 时，能获得的最大价值。**动态规划方程**对于每一件物品 i，我们有两种选择：1. **选择物品 i**：如果背包容量足够容纳物品 i，则选择物品 i 会增加价值 vi，但背包容量减少 wi。因此：```dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi] + vi)```2. **不选择物品 i**：如果不选择物品 i，则背包容量和价值保持与前一步相同：```dp[i][j] = dp[i-1][j]```**初始化*** dp[0][0] = 0，因为没有物品时，背包价值为 0。 * 对于所有 j：dp[0][j] = 0，因为没有物品时，任何容量的背包价值都为 0。 * 对于所有 i：dp[i][0] = 0，因为容量为 0 时，任何物品都无法放入。**计算顺序**我们从 i = 1 开始，逐个考虑每件物品，并从 j = 1 开始，逐个考虑每种容量。**时间复杂度**该解法的时间复杂度为 O(nW)，其中 n 是物品数量，W 是背包容量。**空间复杂度**该解法需要 O(nW) 的空间来存储 dp 数组。**示例**考虑一个背包容量为 5，有 3 件物品的完全背包问题：| 物品 | 重量 (wi) | 价值 (vi) | |---|---|---| | 1 | 1 | 1 | | 2 | 2 | 6 | | 3 | 3 | 10 |**动态规划表**| 容量 \ 物品 | 0 | 1 | 2 | 3 | 4 | 5 | |---|---|---|---|---|---|---| | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 1 | 0 | 1 | 1 | 1 | 1 | 1 | | 2 | 0 | 1 | 6 | 6 | 6 | 6 | | 3 | 0 | 1 | 6 | 10 | 10 | 10 |**最终答案**：最大价值为 10，可通过选择物品 3 一次。