2023年8月1日发(作者：)

c语⾔01背包代码_01背包、完全背包 其实，⼈⽣很多东西⽆所谓最好的，只要是你认为值得就是最好。⼈⽣不是靠情绪活着，⽽是靠⼼态活着。总有看不懂的措辞，不理解的公式，只要你能有所收获，⽆论多少，就是极好。背包问题 是经典的动态规划问题，它⼀共有 9 个分类，建议耐⼼阅读，理解之后你的动态规划⽔平⼀定会有⼀个质的飞跃。背包问题先来浏览⼀下这 9 个问题的名称：1. 01 背包问题2. 完全背包问题3. 多重背包问题4. 混合背包问题5. ⼆维费⽤背包问题6. 分组背包问题7. 背包问题求⽅案数8. 求背包问题的⽅案9. 有依赖的背包问题⾸先，这些问题具有⼀个共同的前提：有 n 个物品和容量为 V 的背包，第 i 件物品的体积为 c[i]，价值为 w[i]。现在的⽬标是确定要将哪些物体放⼊背包，以保证在体积 不超过不超过背包容量 的前提下，背包内的 总价值最⾼背包容量总价值最⾼？其次，基于以上前提条件，通过添加不同的约束条件，就形成了不同的背包问题。1. 01 背包问题 约束条件：每种物品数量为 1，可以选择放或不放状态转移⽅程状态定义：f[i][v] 为前 i 个个 物品中，体积恰好为 v 时的最⼤价值。result = max(f[n][0~V]) 即最终答案，它表⽰前 n 个物品的最⼤价值，假设这时容量为 k ，由于 0 <= k <= V，因此容量要在 0~V求最⼤值来寻找 k。状态转移⽅程：f[i][v] = max(f[i-1][v], f[i-1][v-c[i]] + w[i])以上得到的状态 i 和状态 i-1 关系是从 实际意义实际意义 推断出来的。如果 不选第 i 个物品不选第 i 个物品，那么前 i 个背包的最⼤价值就是前 i-1 个物品的价值，即 f[i][v] = f[i-1][v]；如果 选择了第 i 个物品选择了第 i 个物品，前 i-1 个物品的体积就是 v-c[i]，状态⽅程为 f[i-1][v-c[i]]，注意这时的价值是前 i-1 个物品的价值，因此少了 w[i]的价值，所以 f[i][v] = f[i-1][v-c[i]] + w[i]。最后我们要在这两种情况中选择能使物品最⼤价值更⼤的那个⽅案，故取最⼤值。最终我们就得到了以上的状态转移⽅程。代码实现由于 f[i][v] 是⼆维的，所以我们可以使⽤ ⼆维数组⼆维数组 实现，时间复杂度和空间复杂度均为 O(nV)。伪代码如下：for i = 1, 2, ..., n: # 枚举前 i 个物品 for v = 0, 1, ..., V: # 枚举体积 f[i][v] = f[i-1][v]; # 不选第 i 个物品 if v >= c[i]: # 第 i 个物品的体积必须⼩于 v 才能选 f[i][v] = max(f[i][v], f[i-1][v-c[i]] + w[i])return max(f[n][0...V]) # 返回前 n 个物品的最⼤值优化⽅法然⽽，我们有⼀种优化⽅法，只使⽤⼀维数组来实现，这样可使空间复杂度降到 O(V)。for i = 1, 2, ..., n: # 枚举前 i 个物品 for v = V, V-1, ..., c[i]: # 注意这⾥是倒序遍历， f[v] = max(f[v], f[v-c[i]] + w[i])return f[V] # 返回前 n 个物品时的最⼤值，为体积⼩于等于 V 时的最⼤价值我们发现以上代码有两处优化：1. 去掉了状态 i，且 v 的遍历⽅式改为 倒序倒序 遍历到 c[i]。2. 直接返回 f[V]，没有求最⼤值。为什么能这样优化呢？这⾥理解起来⽐较困难，希望你集中注意⼒，我们来⼀起分析⼀下。⾸先，在优化前，根据代码来看，⼆维数组是这样填满的：⼆维数组转换为⼀维数组⼤致⽰意图如下：对于状态转移⽅程 f[i][v] = max(f[i-1][v], f[i-1][v-c[i]] + w[i])，我们是如何合并 i 这个维度的呢？⾸先对于 max 内的第⼀项 f[i][v] -> f[v]，位置 v 上可能已经存了⼀个值，当我们在原位置进⾏更新时，表明⽤状态 i 的 f[v] 更新掉了状态 i-1时的 f[v]；其次，对于 max 内的第⼆项 f[i-1][v-c[i]] + w[i] -> f[v-c[i]] + w[i]，从下图中可以看出，由于 v 是倒序遍历，f[v-c[i]] 在遍历到 f[v] 时其实已经算过了，只是保存的是 i-1 时的值，当我们继续倒序遍历到 f[v-c[i]] 时，⾃然就将上⼀个状态 i-1 的值进⾏了更新。以上就解决了第⼀处优化涉及的问题，接下来解释第⼆处优化。当我们采⽤优化后的⽅法时，为什么最终返回 f[V] ，⽽不是 max(f[n][0...V]) 呢？实际上当我们进⾏优化时，状态定义状态定义 也同时发⽣了改变：f[v] 表⽰物品体积之和最⼤为 v 时的最⼤价值，⽽⾮恰好为 v 时的最⼤价值。所以我们最后返回 f[V] 就表⽰前 n 个物品，体积之和最⼤为 V 时的最⼤价值，⽆需再求最⼤值。为什么会发⽣这样的变化呢？我们仔细分析数组的维护过程，就能得到答案。对于 v=7 来说，它在每次更新时，总是根据上⼀个状态中的 f[7] 和 f[7-c[i]] 的最⼤值来更新，⽽ c[i] 每次不⼀定相同，这就意味着 f[7] 是由前⼀个 i 的所有⼩于 7 的状态更新⽽来。以上就是第⼆处优化⽅法的解释。相关题⽬322. 零钱兑换⼩结01 背包是背包问题中最基础也是最重要的⼀类问题，讲了这么多，其实能够理解状态⽅程、并且知道它是倒序遍历，⽽完全背包相反，是正序遍历就⾏了，其他的细节可以在做题过程中慢慢体会。2. 完全背包问题 约束条件：每种物品的数量为⽆限个，你可以选择任意数量的物品。状态转移⽅程状态定义：f[i][v] 为前 i 种种 物品中，体积恰好为 v 时的最⼤价值。result = max(f[n][0~V]) 即最终答案，它表⽰前 n 种物品的最⼤价值，假设这时容量为 j ，由于 0 <= j <= V，因此容量要在 0~V求最⼤值来寻找 j。状态转移⽅程：f[i][v] = max(f[i-1][v-k*c[i]] + k*w[i]), 0 <=k*c[i]<=v同样地，以上得到的状态 i 和状态 i-1 关系是从 实际意义实际意义 推断出来的。如果 第 i 个物品选择了 k 次第 i 个物品选择了 k 次，前 i-1 种物品的体积就是 v-k*c[i]，状态⽅程为 f[i-1][v-k*c[i]]，注意这时的价值是前 i-1 种物品的价值，因此少了 k*w[i] 的价值，所以 f[i][v] = max(f[i-1][v-k*c[i]] + k*w[i]), 0 <=k*c[i]<=v。最后我们要在所有不同体积的情况中选择能使物品最⼤价值更⼤的那个⽅案，故取最⼤值。最终我们就得到了以上的状态转移⽅程。优化⽅法我们仍然可以考虑将⼆维数组转化为⼀维数组，与 01 背包优化中“唯⼀”不同的是，这⾥ v 采⽤正序遍历。for i = 1, 2, ..., n: # 枚举前 i 个物品 for v = 0, 1, ..., V: # 注意这⾥是正序遍历， f[v] = max(f[v], f[v-c[i]] + w[i])return f[V] # 返回前 n 个物品时的最⼤值，为体积⼩于等于 V 时的最⼤价值代码中f[v] = max(f[v], f[v-c[i]] + w[i])变为⼆维其实是f[i][v]= max(f[i-1][v],f[i][v-c[i]]+w[i])。这⾥的 max 函数中的第⼆项发⽣了改变，原因在于采⽤了正向遍历 v。我们很容易看到 f[v-c[i]] 就是指状态 i 时的值，⽽⾮ i-1。相关题⽬⾯试题 08.11. 硬币322. 零钱兑换⼩结像本题⼀样，很多类似可以拿⼀个或多个硬币的⽅案数的题⽬都可以将完全背包作为⼀种思路。对于完全背包，只需理解⼆维表⽰和⼀维表⽰中的状态转移⽅程即可，能够独⽴写出代码就可以了，不必有很⼤负担。

2023年8月1日发(作者：)

c语⾔01背包代码_01背包、完全背包 其实，⼈⽣很多东西⽆所谓最好的，只要是你认为值得就是最好。⼈⽣不是靠情绪活着，⽽是靠⼼态活着。总有看不懂的措辞，不理解的公式，只要你能有所收获，⽆论多少，就是极好。背包问题 是经典的动态规划问题，它⼀共有 9 个分类，建议耐⼼阅读，理解之后你的动态规划⽔平⼀定会有⼀个质的飞跃。背包问题先来浏览⼀下这 9 个问题的名称：1. 01 背包问题2. 完全背包问题3. 多重背包问题4. 混合背包问题5. ⼆维费⽤背包问题6. 分组背包问题7. 背包问题求⽅案数8. 求背包问题的⽅案9. 有依赖的背包问题⾸先，这些问题具有⼀个共同的前提：有 n 个物品和容量为 V 的背包，第 i 件物品的体积为 c[i]，价值为 w[i]。现在的⽬标是确定要将哪些物体放⼊背包，以保证在体积 不超过不超过背包容量 的前提下，背包内的 总价值最⾼背包容量总价值最⾼？其次，基于以上前提条件，通过添加不同的约束条件，就形成了不同的背包问题。1. 01 背包问题 约束条件：每种物品数量为 1，可以选择放或不放状态转移⽅程状态定义：f[i][v] 为前 i 个个 物品中，体积恰好为 v 时的最⼤价值。result = max(f[n][0~V]) 即最终答案，它表⽰前 n 个物品的最⼤价值，假设这时容量为 k ，由于 0 <= k <= V，因此容量要在 0~V求最⼤值来寻找 k。状态转移⽅程：f[i][v] = max(f[i-1][v], f[i-1][v-c[i]] + w[i])以上得到的状态 i 和状态 i-1 关系是从 实际意义实际意义 推断出来的。如果 不选第 i 个物品不选第 i 个物品，那么前 i 个背包的最⼤价值就是前 i-1 个物品的价值，即 f[i][v] = f[i-1][v]；如果 选择了第 i 个物品选择了第 i 个物品，前 i-1 个物品的体积就是 v-c[i]，状态⽅程为 f[i-1][v-c[i]]，注意这时的价值是前 i-1 个物品的价值，因此少了 w[i]的价值，所以 f[i][v] = f[i-1][v-c[i]] + w[i]。最后我们要在这两种情况中选择能使物品最⼤价值更⼤的那个⽅案，故取最⼤值。最终我们就得到了以上的状态转移⽅程。代码实现由于 f[i][v] 是⼆维的，所以我们可以使⽤ ⼆维数组⼆维数组 实现，时间复杂度和空间复杂度均为 O(nV)。伪代码如下：for i = 1, 2, ..., n: # 枚举前 i 个物品 for v = 0, 1, ..., V: # 枚举体积 f[i][v] = f[i-1][v]; # 不选第 i 个物品 if v >= c[i]: # 第 i 个物品的体积必须⼩于 v 才能选 f[i][v] = max(f[i][v], f[i-1][v-c[i]] + w[i])return max(f[n][0...V]) # 返回前 n 个物品的最⼤值优化⽅法然⽽，我们有⼀种优化⽅法，只使⽤⼀维数组来实现，这样可使空间复杂度降到 O(V)。for i = 1, 2, ..., n: # 枚举前 i 个物品 for v = V, V-1, ..., c[i]: # 注意这⾥是倒序遍历， f[v] = max(f[v], f[v-c[i]] + w[i])return f[V] # 返回前 n 个物品时的最⼤值，为体积⼩于等于 V 时的最⼤价值我们发现以上代码有两处优化：1. 去掉了状态 i，且 v 的遍历⽅式改为 倒序倒序 遍历到 c[i]。2. 直接返回 f[V]，没有求最⼤值。为什么能这样优化呢？这⾥理解起来⽐较困难，希望你集中注意⼒，我们来⼀起分析⼀下。⾸先，在优化前，根据代码来看，⼆维数组是这样填满的：⼆维数组转换为⼀维数组⼤致⽰意图如下：对于状态转移⽅程 f[i][v] = max(f[i-1][v], f[i-1][v-c[i]] + w[i])，我们是如何合并 i 这个维度的呢？⾸先对于 max 内的第⼀项 f[i][v] -> f[v]，位置 v 上可能已经存了⼀个值，当我们在原位置进⾏更新时，表明⽤状态 i 的 f[v] 更新掉了状态 i-1时的 f[v]；其次，对于 max 内的第⼆项 f[i-1][v-c[i]] + w[i] -> f[v-c[i]] + w[i]，从下图中可以看出，由于 v 是倒序遍历，f[v-c[i]] 在遍历到 f[v] 时其实已经算过了，只是保存的是 i-1 时的值，当我们继续倒序遍历到 f[v-c[i]] 时，⾃然就将上⼀个状态 i-1 的值进⾏了更新。以上就解决了第⼀处优化涉及的问题，接下来解释第⼆处优化。当我们采⽤优化后的⽅法时，为什么最终返回 f[V] ，⽽不是 max(f[n][0...V]) 呢？实际上当我们进⾏优化时，状态定义状态定义 也同时发⽣了改变：f[v] 表⽰物品体积之和最⼤为 v 时的最⼤价值，⽽⾮恰好为 v 时的最⼤价值。所以我们最后返回 f[V] 就表⽰前 n 个物品，体积之和最⼤为 V 时的最⼤价值，⽆需再求最⼤值。为什么会发⽣这样的变化呢？我们仔细分析数组的维护过程，就能得到答案。对于 v=7 来说，它在每次更新时，总是根据上⼀个状态中的 f[7] 和 f[7-c[i]] 的最⼤值来更新，⽽ c[i] 每次不⼀定相同，这就意味着 f[7] 是由前⼀个 i 的所有⼩于 7 的状态更新⽽来。以上就是第⼆处优化⽅法的解释。相关题⽬322. 零钱兑换⼩结01 背包是背包问题中最基础也是最重要的⼀类问题，讲了这么多，其实能够理解状态⽅程、并且知道它是倒序遍历，⽽完全背包相反，是正序遍历就⾏了，其他的细节可以在做题过程中慢慢体会。2. 完全背包问题 约束条件：每种物品的数量为⽆限个，你可以选择任意数量的物品。状态转移⽅程状态定义：f[i][v] 为前 i 种种 物品中，体积恰好为 v 时的最⼤价值。result = max(f[n][0~V]) 即最终答案，它表⽰前 n 种物品的最⼤价值，假设这时容量为 j ，由于 0 <= j <= V，因此容量要在 0~V求最⼤值来寻找 j。状态转移⽅程：f[i][v] = max(f[i-1][v-k*c[i]] + k*w[i]), 0 <=k*c[i]<=v同样地，以上得到的状态 i 和状态 i-1 关系是从 实际意义实际意义 推断出来的。如果 第 i 个物品选择了 k 次第 i 个物品选择了 k 次，前 i-1 种物品的体积就是 v-k*c[i]，状态⽅程为 f[i-1][v-k*c[i]]，注意这时的价值是前 i-1 种物品的价值，因此少了 k*w[i] 的价值，所以 f[i][v] = max(f[i-1][v-k*c[i]] + k*w[i]), 0 <=k*c[i]<=v。最后我们要在所有不同体积的情况中选择能使物品最⼤价值更⼤的那个⽅案，故取最⼤值。最终我们就得到了以上的状态转移⽅程。优化⽅法我们仍然可以考虑将⼆维数组转化为⼀维数组，与 01 背包优化中“唯⼀”不同的是，这⾥ v 采⽤正序遍历。for i = 1, 2, ..., n: # 枚举前 i 个物品 for v = 0, 1, ..., V: # 注意这⾥是正序遍历， f[v] = max(f[v], f[v-c[i]] + w[i])return f[V] # 返回前 n 个物品时的最⼤值，为体积⼩于等于 V 时的最⼤价值代码中f[v] = max(f[v], f[v-c[i]] + w[i])变为⼆维其实是f[i][v]= max(f[i-1][v],f[i][v-c[i]]+w[i])。这⾥的 max 函数中的第⼆项发⽣了改变，原因在于采⽤了正向遍历 v。我们很容易看到 f[v-c[i]] 就是指状态 i 时的值，⽽⾮ i-1。相关题⽬⾯试题 08.11. 硬币322. 零钱兑换⼩结像本题⼀样，很多类似可以拿⼀个或多个硬币的⽅案数的题⽬都可以将完全背包作为⼀种思路。对于完全背包，只需理解⼆维表⽰和⼀维表⽰中的状态转移⽅程即可，能够独⽴写出代码就可以了，不必有很⼤负担。