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

0-1背包问题的Python实现及其优化1. 概述有⼀个背包，它的容量为C (Capacity)。现在有n种不同的物品，编号为0…n-1，其中每⼀件物品的重量为w(i)，价值为v(i)。 问可以向这个背包中盛放哪些物品，使得在不超过背包容量的基础上，物品的总价值最⼤。暴⼒解法: 每⼀件物品都可以放进背包，也可以不放进背包。时间复杂度为：O((2^n)*n)另辟蹊径： F(n, C)考虑将n个物品放进容量为C的背包，使得价值最⼤。⼀件物品只有选与不选两种情况，也即每件物品只能选⼀次。（1）当不考虑选取第 i 件物品时，F(i, C) = F(i - 1, C)；（2）当考虑选取第 i 件物品时，F(i, C) = v(i) + F(i - 1, C - w(i))要在上述两种情况中取最⼤值，所以状态转移⽅程即为：F(i, C) = max( F(i - 1, C), v(i) + F(i - 1, C - w(i)) )2. 第⼀种⽅法——记忆化搜索（1）主函数中传⼊w数组（每个物品的容量），v数组（每个物品的价值）和C（背包的总容量）（2）使⽤⼀个递归函数bestValue，在这个函数中⾸先传⼊w和v，index表⽰考虑到的物品的序列号，以及要处理的背包容量C（bestValue的含义就是⽤[0…index]的物品，填充容积为C的背包的最⼤价值）⾸先看递归的终⽌条件：若当前的index<0，也就是说此时物品的集合是⼀个空集了，选不出任何东西了 或者 当前的背包容量c<=0，也就是说⽆法装⼊任何新的物品了，此时就应该返回0 （简单点说就是⽆法选物品或⽆法装物品）否则就要尝试向背包中放⼊新的物品：考虑物品集合中的最后⼀个物品index该不该放进去（1）⼀是这个物品根本不去管——bestValue(w, v, index-1, c)（2）⼆是将这个index物品放进背包⾥，为了保险起见，此处需先确定当前背包的容量⼤于等于index物品的容积（if c>= w[index]），这时的价值就是v[index] + bestValue(w, v, index-1, c - w[index])要将两者取最⼤值给res，返回res即可。但是⼜存在重叠⼦问题，来源于index和c构成了⼀个数据对，求解过程中同样的数据对可能出现多次，因此可以⽤记忆化搜索。由于背包问题有两个约束条件（w和v），每个状态是被两个变量所定义的，所以开辟的记忆化空间应该是⼀个⼆维数组

memo=[[-1 for j in range(C+1)] fori in range(n)] （⼀共有n⾏，C+1列（来表⽰从0到C这么多的容量））递归终⽌条件依然不变；否则就要看 memo[index][c] 这个状态之前有没有被计算过，若被计算过，直接返回 memo[index][c] 即可；否则才运⾏下⾯的逻辑，计算出来res之后，还要将res的值记录下来（memo[index][c]=res），最后返回res即可。class Knapsack01: def knapsack01(self, w, v, C): n = len(w) = [[-1 for j in range(C + 1)] for i in range(n)] return lue(w, v, n-1, C) def bestValue(self, w, v, index, c): if index < 0 or c <= 0: return 0 if [index][c] != -1: return [index][c] res = lue(w, v, index-1, c) if c >= w[index]: res = max(res, v[index] + lue(w, v, index - 1, c - w[index])) [index][c] = res return resk = Knapsack01()w = [1, 2, 3]v = [6, 10, 12]C = 5print(ck01(w, v, C))输出：223. 第⼆种⽅法——动态规划使⽤动态规划，依旧是先确定n的数值（n=len(w))，注意： 我们传⼊了两个数组w和v，那么这两个数组所含有的元素个数应该是⼀样的：assert(len(w) == len(v))，有了n之后就可以设⽴动态规划的⼆维数组，有n⾏，每⼀⾏有C+1列（从0到C）memo=[[-1 for j in range(C+1)]for i in range(n)]动态规划是⾃底向上的，所以我们先处理最基础的问题：先看memo第0⾏的每个元素是多少，进⾏⼀个for循环遍历列：for j inrange(0, C+1)，memo[0][j]⾥的j表⽰此时处理的背包容量，只考虑0号物体 ，所以将j的⼤⼩和w[0]进⾏⽐较，若j>=w[0]，就能将0号物品放进去，最⼤值就是v[0]；否则的话背包中⽆法放⼊物品，最⼤值就是0，为了保险起见，需要添加上若n=0（也即传进来的w和v中没有任何元素），直接返回0即可。最基础的问题解决了，剩下的问题就是⼀个递推的过程，现在是逐⾏的解决问题：for i in range(1, n+1)（因为基础问题已经处理过第0⾏，所以此处从第1⾏开始），在每⾏中逐列的解决问题：for j in range(0, C+1)，在每⼀列中要处理的是计算memo[i][j]（考虑0~i这些物品且容积为j的背包获得的最⼤值）的值：（1）第⼀种情况是不考虑 i，直接memo[i][j] = memo[i-1][j]；（2）第⼆种情况是考虑 i，但需要判断此时的容量 j 是否⼤于等于w[i]（即第 i 个物品确实能放进背包中）——memo[i][j] = max(memo[i][j], v[i] + memo[i-1][j-v[i]])整个循环⼀直进⾏下去，直到求出memo[n-1][C]，直接返回该值即可。使⽤for x in memo可以很清晰的查看 memo 这个⼆维数组中的每个数字，右下⾓的最后⼀个数即为所求。class Knapsack01: def knapsack01(self, w, v, C): assert (len(w) == len(v)) n = len(w) if n == 0: return 0 memo = [[-1 for j in range(C + 1)] for i in range(n)] for j in range(0, C + 1): memo[0][j] = v[0] if j >= w[0] else 0 for i in range(1, n): for j in range(0, C + 1): memo[i][j] = memo[i - 1][j] if j >= w[i]: memo[i][j] = max(memo[i][j], v[i] + memo[i - 1][j - w[i]]) for x in memo: print(x) return memo[n - 1][C]k = Knapsack01()w = [1, 2, 3]v = [6, 10, 12]C = 5print(ck01(w, v, C))输出：[0, 6, 6, 6, 6, 6][0, 6, 10, 16, 16, 16][0, 6, 10, 16, 18, 22]224. 优化算法空间（只使⽤两⾏）上述动态规划的时间复杂度为O(n * C)，空间复杂度为O(n * C)。但实际上第 i ⾏元素只依赖于第 i-1 ⾏元素，理论上，只需要保持两⾏元素即可，不需要保持n⾏元素，这样可以优化空间，空间复杂度为O(2 * C)。开辟两⾏空间，最开始第⼀⾏是 i=0，第⼆⾏处理 i=1 的情况，依靠第⼀⾏ i=0 的数据，处理完毕后接着处理 i=2 的情况（i=2 这⼀⾏的元素是依靠 i=1这⾏的元素，与 i=0 这⾏⽆关）所以可以将 i=2 覆盖掉 i=0这⾏……以此类推，可以发现，第⼀⾏永远处理的是 i 为偶数时的情况，第⼆⾏永远处理的是 i 为奇数时的情况。具体实现如下：⾸先⼀开始定义memo这个⼆维数组时，改成两⾏即可

memo = [[-1 for j in range(C+1)] for i in range(2)]；接下来初始化i=0的这⼀⾏不需要变动，重点是下⾯的循环，我们还是从i=1开始⼀直到n依次来更新每⼀⾏，在更新的过程中，对于第i⾏来说，实际上使⽤的是memo这个⼆维空间中的 i%2 那⼀⾏（不是第0⾏就是第1⾏，具体是哪⼀⾏让它和2求余数，i为偶数时在第0⾏，为奇数时在第1⾏），所以就有了

memo[i%2][j] = memo[(i-1)%2][j]，表⽰第i⾏还是要根据第i-1⾏来，但是我们的物理空间中只有两⾏，那么第i⾏现在在 i%2 这个位置，第i-1⾏在(i-1)%2这个位置，下⾯以此类推，⼀旦涉及到memo的⾏号，都要将它%2；最后返回的是memo[(n-1)%2][C]，我们依然是要将第n-1⾏的第C个元素返回回去，只不过当前的物理存储中，第n-1⾏是在 (n-1)%2这个位置。class Knapsack01: def knapsack01(self, w, v, C): assert (len(w) == len(v) and C >= 0) n = len(w) if n == 0 or C == 0: return 0 memo = [[-1 for j in range(C + 1)] for i in range(2)] for j in range(0, C + 1): memo[0][j] = v[0] if j >= w[0] else 0 for i in range(1, n): for j in range(0, C + 1): memo[i % 2][j] = memo[(i - 1) % 2][j] if j >= w[i]: memo[i % 2][j] = max(memo[i % 2][j], v[i] + memo[(i - 1) % 2][j - w[i]]) return memo[(n - 1) % 2][C]k = Knapsack01()w = [1, 2, 3]v = [6, 10, 12]C = 5print(ck01(w, v, C))输出：22注意：这个优化使得我们可以处理的背包容量⽐原先⼤很多，举例⼦：假设我们有100个物品，背包容量为100，此时的空间就达到了极限，原来使⽤n*C的空间复杂度，我们的空间最多有100 * 100=10000个单元，但使⽤这个优化后，我们可以将这10000个空间重新分配10000=2 * 5000，换句话说，我们依然可以处理有100个物品的背包问题，但是此时我们处理的背包容量的最⼤限额达到了5000。5. 进⼀步优化算法空间（只使⽤⼀⾏）如何只使⽤⼀⾏⼤⼩为C的数组完成动态规划？先看两⾏的，对于上⼀⾏，我们永远只使⽤正上⽅和左边的元素，右边的不会去碰，就提⽰了我们，如果只有⼀⾏，在之前的逻辑中每⼀次更新只参考上⾯和左边的内容，所以我们可以从右往左的刷新这⼀⾏的内容。⽐如：下图初始化的是 i = 0 这⾏的内容我们要更新 i = 1 这⾏的内容，就从最后⼀列开始，背包容量为5时，可以放下编号为1的物品（重量为2，价值为10），这时就有两种情况：（1）不放编号为1的物品时，直接把上⼀⾏该列的数字拿过来，也就是此时的价值为6；（2）放⼊编号为1的物品时，就是v[i] +memo[i - 1][j - w[i]]，也就是将编号为1的物品价值10 加上 上⼀⾏（第0⾏）第3列的数值6 等于16。取两者之间的最⼤值16放⼊最后⼀个数字的位置…依次类推不断向前更新数值，直到当前的容量⽆法再装下当前的物品。具体实现如下：memo就初始化为⼀维数组：memo = [-1 for i in range(C + 1)]；下⾯看初始化的过程，⾸先对第⼀⾏的内容进⾏初始化（也就是i=0时的值进⾏初始化），因为是⼀维数组，直接写成memo[j] = v[0] if j>=w[0] else 0；紧接着我们对i=1开始⼀直到n依次求解，在求解的过程中我们对列的处理，每次都是从C开始的，⼀直向前处理，直到j⼤于等于当前要处理的物品的重量for j in range(C, w[i] - 1, -1)，因为当 j ⽐ w[i] ⼩时，说明当前物品已经不能放⼊背包⾥了，那么当前⾏中停留的那些j= 0) n = len(w) if n == 0 or C == 0: return 0 memo = [-1 for i in range(C + 1)] for j in range(0, C + 1): memo[j] = v[0] if j >= w[0] else 0 for i in range(1, n): for j in range(C, w[i] - 1, -1): memo[j] = max(memo[j], v[i] + memo[j - w[i]]) return memo[C]k = Knapsack01()w = [1, 2, 3]v = [6, 10, 12]C = 5print(ck01(w, v, C))输出：22

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

0-1背包问题的Python实现及其优化1. 概述有⼀个背包，它的容量为C (Capacity)。现在有n种不同的物品，编号为0…n-1，其中每⼀件物品的重量为w(i)，价值为v(i)。 问可以向这个背包中盛放哪些物品，使得在不超过背包容量的基础上，物品的总价值最⼤。暴⼒解法: 每⼀件物品都可以放进背包，也可以不放进背包。时间复杂度为：O((2^n)*n)另辟蹊径： F(n, C)考虑将n个物品放进容量为C的背包，使得价值最⼤。⼀件物品只有选与不选两种情况，也即每件物品只能选⼀次。（1）当不考虑选取第 i 件物品时，F(i, C) = F(i - 1, C)；（2）当考虑选取第 i 件物品时，F(i, C) = v(i) + F(i - 1, C - w(i))要在上述两种情况中取最⼤值，所以状态转移⽅程即为：F(i, C) = max( F(i - 1, C), v(i) + F(i - 1, C - w(i)) )2. 第⼀种⽅法——记忆化搜索（1）主函数中传⼊w数组（每个物品的容量），v数组（每个物品的价值）和C（背包的总容量）（2）使⽤⼀个递归函数bestValue，在这个函数中⾸先传⼊w和v，index表⽰考虑到的物品的序列号，以及要处理的背包容量C（bestValue的含义就是⽤[0…index]的物品，填充容积为C的背包的最⼤价值）⾸先看递归的终⽌条件：若当前的index<0，也就是说此时物品的集合是⼀个空集了，选不出任何东西了 或者 当前的背包容量c<=0，也就是说⽆法装⼊任何新的物品了，此时就应该返回0 （简单点说就是⽆法选物品或⽆法装物品）否则就要尝试向背包中放⼊新的物品：考虑物品集合中的最后⼀个物品index该不该放进去（1）⼀是这个物品根本不去管——bestValue(w, v, index-1, c)（2）⼆是将这个index物品放进背包⾥，为了保险起见，此处需先确定当前背包的容量⼤于等于index物品的容积（if c>= w[index]），这时的价值就是v[index] + bestValue(w, v, index-1, c - w[index])要将两者取最⼤值给res，返回res即可。但是⼜存在重叠⼦问题，来源于index和c构成了⼀个数据对，求解过程中同样的数据对可能出现多次，因此可以⽤记忆化搜索。由于背包问题有两个约束条件（w和v），每个状态是被两个变量所定义的，所以开辟的记忆化空间应该是⼀个⼆维数组

memo=[[-1 for j in range(C+1)] fori in range(n)] （⼀共有n⾏，C+1列（来表⽰从0到C这么多的容量））递归终⽌条件依然不变；否则就要看 memo[index][c] 这个状态之前有没有被计算过，若被计算过，直接返回 memo[index][c] 即可；否则才运⾏下⾯的逻辑，计算出来res之后，还要将res的值记录下来（memo[index][c]=res），最后返回res即可。class Knapsack01: def knapsack01(self, w, v, C): n = len(w) = [[-1 for j in range(C + 1)] for i in range(n)] return lue(w, v, n-1, C) def bestValue(self, w, v, index, c): if index < 0 or c <= 0: return 0 if [index][c] != -1: return [index][c] res = lue(w, v, index-1, c) if c >= w[index]: res = max(res, v[index] + lue(w, v, index - 1, c - w[index])) [index][c] = res return resk = Knapsack01()w = [1, 2, 3]v = [6, 10, 12]C = 5print(ck01(w, v, C))输出：223. 第⼆种⽅法——动态规划使⽤动态规划，依旧是先确定n的数值（n=len(w))，注意： 我们传⼊了两个数组w和v，那么这两个数组所含有的元素个数应该是⼀样的：assert(len(w) == len(v))，有了n之后就可以设⽴动态规划的⼆维数组，有n⾏，每⼀⾏有C+1列（从0到C）memo=[[-1 for j in range(C+1)]for i in range(n)]动态规划是⾃底向上的，所以我们先处理最基础的问题：先看memo第0⾏的每个元素是多少，进⾏⼀个for循环遍历列：for j inrange(0, C+1)，memo[0][j]⾥的j表⽰此时处理的背包容量，只考虑0号物体 ，所以将j的⼤⼩和w[0]进⾏⽐较，若j>=w[0]，就能将0号物品放进去，最⼤值就是v[0]；否则的话背包中⽆法放⼊物品，最⼤值就是0，为了保险起见，需要添加上若n=0（也即传进来的w和v中没有任何元素），直接返回0即可。最基础的问题解决了，剩下的问题就是⼀个递推的过程，现在是逐⾏的解决问题：for i in range(1, n+1)（因为基础问题已经处理过第0⾏，所以此处从第1⾏开始），在每⾏中逐列的解决问题：for j in range(0, C+1)，在每⼀列中要处理的是计算memo[i][j]（考虑0~i这些物品且容积为j的背包获得的最⼤值）的值：（1）第⼀种情况是不考虑 i，直接memo[i][j] = memo[i-1][j]；（2）第⼆种情况是考虑 i，但需要判断此时的容量 j 是否⼤于等于w[i]（即第 i 个物品确实能放进背包中）——memo[i][j] = max(memo[i][j], v[i] + memo[i-1][j-v[i]])整个循环⼀直进⾏下去，直到求出memo[n-1][C]，直接返回该值即可。使⽤for x in memo可以很清晰的查看 memo 这个⼆维数组中的每个数字，右下⾓的最后⼀个数即为所求。class Knapsack01: def knapsack01(self, w, v, C): assert (len(w) == len(v)) n = len(w) if n == 0: return 0 memo = [[-1 for j in range(C + 1)] for i in range(n)] for j in range(0, C + 1): memo[0][j] = v[0] if j >= w[0] else 0 for i in range(1, n): for j in range(0, C + 1): memo[i][j] = memo[i - 1][j] if j >= w[i]: memo[i][j] = max(memo[i][j], v[i] + memo[i - 1][j - w[i]]) for x in memo: print(x) return memo[n - 1][C]k = Knapsack01()w = [1, 2, 3]v = [6, 10, 12]C = 5print(ck01(w, v, C))输出：[0, 6, 6, 6, 6, 6][0, 6, 10, 16, 16, 16][0, 6, 10, 16, 18, 22]224. 优化算法空间（只使⽤两⾏）上述动态规划的时间复杂度为O(n * C)，空间复杂度为O(n * C)。但实际上第 i ⾏元素只依赖于第 i-1 ⾏元素，理论上，只需要保持两⾏元素即可，不需要保持n⾏元素，这样可以优化空间，空间复杂度为O(2 * C)。开辟两⾏空间，最开始第⼀⾏是 i=0，第⼆⾏处理 i=1 的情况，依靠第⼀⾏ i=0 的数据，处理完毕后接着处理 i=2 的情况（i=2 这⼀⾏的元素是依靠 i=1这⾏的元素，与 i=0 这⾏⽆关）所以可以将 i=2 覆盖掉 i=0这⾏……以此类推，可以发现，第⼀⾏永远处理的是 i 为偶数时的情况，第⼆⾏永远处理的是 i 为奇数时的情况。具体实现如下：⾸先⼀开始定义memo这个⼆维数组时，改成两⾏即可

memo = [[-1 for j in range(C+1)] for i in range(2)]；接下来初始化i=0的这⼀⾏不需要变动，重点是下⾯的循环，我们还是从i=1开始⼀直到n依次来更新每⼀⾏，在更新的过程中，对于第i⾏来说，实际上使⽤的是memo这个⼆维空间中的 i%2 那⼀⾏（不是第0⾏就是第1⾏，具体是哪⼀⾏让它和2求余数，i为偶数时在第0⾏，为奇数时在第1⾏），所以就有了

memo[i%2][j] = memo[(i-1)%2][j]，表⽰第i⾏还是要根据第i-1⾏来，但是我们的物理空间中只有两⾏，那么第i⾏现在在 i%2 这个位置，第i-1⾏在(i-1)%2这个位置，下⾯以此类推，⼀旦涉及到memo的⾏号，都要将它%2；最后返回的是memo[(n-1)%2][C]，我们依然是要将第n-1⾏的第C个元素返回回去，只不过当前的物理存储中，第n-1⾏是在 (n-1)%2这个位置。class Knapsack01: def knapsack01(self, w, v, C): assert (len(w) == len(v) and C >= 0) n = len(w) if n == 0 or C == 0: return 0 memo = [[-1 for j in range(C + 1)] for i in range(2)] for j in range(0, C + 1): memo[0][j] = v[0] if j >= w[0] else 0 for i in range(1, n): for j in range(0, C + 1): memo[i % 2][j] = memo[(i - 1) % 2][j] if j >= w[i]: memo[i % 2][j] = max(memo[i % 2][j], v[i] + memo[(i - 1) % 2][j - w[i]]) return memo[(n - 1) % 2][C]k = Knapsack01()w = [1, 2, 3]v = [6, 10, 12]C = 5print(ck01(w, v, C))输出：22注意：这个优化使得我们可以处理的背包容量⽐原先⼤很多，举例⼦：假设我们有100个物品，背包容量为100，此时的空间就达到了极限，原来使⽤n*C的空间复杂度，我们的空间最多有100 * 100=10000个单元，但使⽤这个优化后，我们可以将这10000个空间重新分配10000=2 * 5000，换句话说，我们依然可以处理有100个物品的背包问题，但是此时我们处理的背包容量的最⼤限额达到了5000。5. 进⼀步优化算法空间（只使⽤⼀⾏）如何只使⽤⼀⾏⼤⼩为C的数组完成动态规划？先看两⾏的，对于上⼀⾏，我们永远只使⽤正上⽅和左边的元素，右边的不会去碰，就提⽰了我们，如果只有⼀⾏，在之前的逻辑中每⼀次更新只参考上⾯和左边的内容，所以我们可以从右往左的刷新这⼀⾏的内容。⽐如：下图初始化的是 i = 0 这⾏的内容我们要更新 i = 1 这⾏的内容，就从最后⼀列开始，背包容量为5时，可以放下编号为1的物品（重量为2，价值为10），这时就有两种情况：（1）不放编号为1的物品时，直接把上⼀⾏该列的数字拿过来，也就是此时的价值为6；（2）放⼊编号为1的物品时，就是v[i] +memo[i - 1][j - w[i]]，也就是将编号为1的物品价值10 加上 上⼀⾏（第0⾏）第3列的数值6 等于16。取两者之间的最⼤值16放⼊最后⼀个数字的位置…依次类推不断向前更新数值，直到当前的容量⽆法再装下当前的物品。具体实现如下：memo就初始化为⼀维数组：memo = [-1 for i in range(C + 1)]；下⾯看初始化的过程，⾸先对第⼀⾏的内容进⾏初始化（也就是i=0时的值进⾏初始化），因为是⼀维数组，直接写成memo[j] = v[0] if j>=w[0] else 0；紧接着我们对i=1开始⼀直到n依次求解，在求解的过程中我们对列的处理，每次都是从C开始的，⼀直向前处理，直到j⼤于等于当前要处理的物品的重量for j in range(C, w[i] - 1, -1)，因为当 j ⽐ w[i] ⼩时，说明当前物品已经不能放⼊背包⾥了，那么当前⾏中停留的那些j= 0) n = len(w) if n == 0 or C == 0: return 0 memo = [-1 for i in range(C + 1)] for j in range(0, C + 1): memo[j] = v[0] if j >= w[0] else 0 for i in range(1, n): for j in range(C, w[i] - 1, -1): memo[j] = max(memo[j], v[i] + memo[j - w[i]]) return memo[C]k = Knapsack01()w = [1, 2, 3]v = [6, 10, 12]C = 5print(ck01(w, v, C))输出：22