【动态规划part06】| 完全背包理论基础、518.零钱兑换||、组合总和|V

**动态规划 Part06: 完全背包理论基础、518. 零钱兑换 ||, 组合总和**

在前面的文章中，我们已经学习了动态规划的基本概念、算法设计思想以及一些经典问题的解决方案。今天，我们将继续深入探讨完全背包问题及其相关问题。

**1. 完全背包问题**

完全背包问题是指给定一个物品集合和一个背包容量，要求在不超过背包容量的情况下，将物品放入背包中，以获得最大价值。这个问题的典型例子是零钱兑换。

**2. 零钱兑换**

零钱兑换是完全背包问题的一个经典例子。在这个问题中，我们需要将给定的金额以最少数量的硬币兑换出来。例如，给定11 美元，我们可以使用10 美元 +1 美元 =11 美元 的方式来兑换。

**3. 组合总和**

组合总和是另一个与完全背包相关的问题。在这个问题中，我们需要找到一组数字的所有可能组合，组合之和等于给定的目标值。例如，给定 [2,3,6] 和 targetSum =7，我们可以使用以下组合来达到目标：[2,2,3]、[3,4]（不合法，因为4 不在集合中）、[3,6]。

**完全背包问题的解决方案**

我们将使用动态规划来解决完全背包问题。首先，我们需要定义一个状态转移方程来表示当前状态下的最大价值。

假设 `dp[i][j]` 表示前 `i` 个物品和背包容量为 `j` 的最大价值。

对于每个物品 `i`，我们有两种选择：

1. 不放入物品 `i`：此时，我们的状态转移方程为 `dp[i][j] = dp[i-1][j]`
2. 放入物品 `i`：此时，我们需要检查背包容量是否足够大，以便放入物品 `i`。如果是，则我们可以将物品 `i` 的价值加到当前状态的最大价值中。

因此，状态转移方程为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])

其中 `weight[i]` 是物品 `i` 的重量，`value[i]` 是物品 `i` 的价值。

**零钱兑换的解决方案**

对于零钱兑换问题，我们可以使用完全背包问题的状态转移方程来求解。我们需要定义一个状态转移方程来表示当前金额下的最少硬币数量。

假设 `dp[i][j]` 表示金额为 `i` 的最少硬币数量。

对于每个硬币 `j`，我们有两种选择：

1. 不使用硬币 `j`：此时，我们的状态转移方程为 `dp[i][j] = dp[i][j-1]`
2. 使用硬币 `j`：此时，我们需要检查金额是否足够大，以便使用硬币 `j`。如果是，则我们可以将硬币 `j` 的数量加到当前状态的最少硬币数量中。

因此，状态转移方程为：

dp[i][j] = min(dp[i][j-1], dp[i-j][j-1] +1)

其中 `i-j` 表示使用硬币 `j` 后剩余的金额。

**组合总和的解决方案**

对于组合总和问题，我们可以使用完全背包问题的状态转移方程来求解。我们需要定义一个状态转移方程来表示当前目标值下的所有可能组合。

假设 `dp[i][j]` 表示目标值为 `i` 的所有可能组合。

对于每个数字 `j`，我们有两种选择：

1. 不使用数字 `j`：此时，我们的状态转移方程为 `dp[i][j] = dp[i][j-1]`
2. 使用数字 `j`：此时，我们需要检查目标值是否足够大，以便使用数字 `j`。如果是，则我们可以将数字 `j` 的组合加到当前状态的所有可能组合中。

因此，状态转移方程为：

dp[i][j] = max(dp[i][j-1], dp[i-j][j-1])

其中 `i-j` 表示使用数字 `j` 后剩余的目标值。

**总结**

在本文中，我们学习了完全背包问题及其相关问题，包括零钱兑换和组合总和。我们使用动态规划来解决这些问题，并提供了状态转移方程和代码示例。