背包入门\COLOR{ORANGE}{\TEXTBF{背包}}\COLOR{SKYBLUE}{入门}背包入门
> C++ 中的 0/10/10/1 背包和完全完全完全背包问题。这两个问题都是经典的动态规划问题，涉及到如何在给定背包容量和物品重量、价值的情况下，选择最优的物品放入背包以获得最大的总价值。
0/1背包问题\COLOR{BLUE}{0}/\COLOR{RED}{1} \COLOR{ORANGE}{\TEXTBF{背包问题}}0/1背包问题
问题描述
0/1背包问题\color{blue}{0}/\color{red}{1} \color{orange}{\textbf{背包问题}}0/1背包问题是一个经典的动态规划问题，指的是有 n 个物品和一个容量为 W 的背包，每个物品只能选择装入一次或不装入。目标是在不超过背包容量的前提下，选择物品使得背包中物品的总价值最大。
解法思路
1. 定义数组元素含义： 我们定义一个二维数组 dp[i][j]，表示在前 i 个物品中任取物品，放进容量为 j 的背包中，背包所能装的最大价值。
2. 递推关系式： 对于每个物品 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])
3. 初始化： 初始化第一行和第一列为 0。
4. 填表格： 根据递推公式填充整个二维数组。
5. 求解最终结果： 最终结果为 dp[n][W]，其中 n 是物品数量，W 是背包容量。
代码实现
以下是 C++ 中 0/1背包问题\color{blue}{0}/\color{red}{1} \color{orange}{\textbf{背包问题}}0/1背包问题的代码示例：
完全背包问题\COLOR{PURPLE}{\TEXTBF{完全}} \COLOR{ORANGE}{\TEXTBF{背包问题}}完全背包问题
问题描述
完全背包问题与 0/1背包问题\color{blue}{0}/\color{red}{1} \color{orange}{\textbf{背包问题}}0/1背包问题类似，但不同之处在于每种物品的数量是无限\textbf{无限}无限的。也就是说，每个物品可以选择装入多次。
解法思路
1. 定义数组元素含义： 我们仍然定义一个一维数组 dp[j]，表示在前 i 个物品中任取物品，放进容量为 j 的背包中，背包所能装的最大价值。
2. 递推关系式： 对于每个物品 i，有两种选择：放入背包或不放入背包。因此递推公式如下：
* 不放第 i 个物品：dp[j] = dp[j]
* 放第 i 个物品：dp[j] = max(dp[j], dp[j-w[i]] + v[i])
3. 初始化： 初始化一维数组 dp[j] 为 0。
4. 填表格： 从前向后遍历背包容量，根据递推公式更新 dp[j]。
5. 求解最终结果： 最终结果为 dp[W]，其中 W 是背包容量。
代码实现
以下是 C++ 中完全背包问题\color{purple}{\textbf{完全}} \color{orange}{\textbf{背包问题}}完全背包问题的代码示例：
这段代码中，我们使用了一维数组 dp[j] 来记录背包容量为 j 时的最大价值。通过遍历物品和背包容量，不断更新 dp[j] 的值，最终得到完全背包问题\color{purple}{\textbf{完全}} \color{orange}{\textbf{背包问题}}完全背包问题的最优解。
