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

背包问题及其变型（python）

1. 0，1问题⼀个背包，往⾥装东西，重量w(weight)分别为为[2,3,4,5] 价值v(value)对应为[3,4,5,6] 如果你的容量为8,每个物品只有⼀个，求你能装⼊背包的最⼤价值我们可以⼀步⼀步来 ，先创建⼀个表格 (数组), 数组dp[i][j] i代表你只⽤前i个物体，j代表你的剩余容量，dp[i][j] 代表在此情况下可以得到的最⼤价值，先得到⼀个表格先填第⼀⾏(也就是假设现在你只有第⼀个物体), ⾸先第⼀个物体重量为2 剩余容量为1，剩余容量⼩于物体重量，则最⼤价值为0， 第⼆个数剩余容量=物体容量，可以拿 填上第⼀个物体的价值3 就这样填上第⼀⾏ ， 继续填第⼆⾏ 第⼆⾏代表的意义就是我们现在可以使⽤的有两个物体了，使⽤这两个物体能够得到的最⼤价值。这⼀共可以分为两种情况，⼀种是放第⼆个物体，⼀种是不放第⼆个物体，选择其中⼤的，转移⽅程为dp[i][j] = max(dp[ i - 1, j ], dp[ i - 1, j - w[ i ] ] + v [ i ] ) 这⾥解释下放第⼆个物体的式⼦，dp[ i-1, j - w[ i ] ]代表你把第⼆个物体的容量空出来时，能得到的最⼤价值， 再加上这个物体的价值。就这样填好所有的。则 表格中最后⼀个物体就是⾯对所有物体，剩余容量为C时能得到的最⼤价值了。def pack1(w, v, C): #每个东西只能选择⼀次 dp = [[0 for _ in range(C+1)] for _ in range(len(w)+1)] for i in range(1, len(w)+1): for j in range(1, C+1): if j < w[i-1]: #如果剩余容量不够新来的物体 直接等于之前的 dp[i][j] = dp[i-1][j] else: dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]]+ v[i-1]) return dp[len(w)][c]这个是得到的dp结果观察发现，可以对它的空间复杂度进⾏优化，我们可以⽤⼀维数组只保存最后⼀⾏, 代码如下def pack1(w, v, c): #它是先得到第⼀⾏的值，存到dp中，然后再直接⽤dp相当于就是上⼀⾏的值，所以下⾯必须⽤逆序 #否则dp[j-w[i-1]]可能会⽤到你本⾏的值，从⼤到⼩就不会 dp = [0 for _ in range(c+1)] for i in range(1, len(w)+1): for j in reversed(range(1, c+1)):#这⾥必须⽤逆序 if w[i-1] <= j: dp[j] = max(dp[j], dp[j-w[i-1]]+v[i-1]) return dp[c]2 背包问题变形：完全背包问题还是原来的问题，上次是每个物体只能⽤1次，现在改成⽆限次，转移⽅程只需要修改⼀点即可dp[i][j] = max(dp[ i - 1, j ], dp[ i, j - w[ i ]] + v [ i ] ) 只需要把后⾯的i-1 -> i 即可def pack2(w, v, C): #每个东西能选择多次 完全背包问题 dp = [[0 for _ in range(C+1)] for _ in range(len(w)+1)] for i in range(1, len(w)+1): for j in range(1, C+1): if j < w[i-1]: dp[i][j] = dp[i-1][j] else: dp[i][j] = max(dp[i-1][j], dp[i][j-w[i-1]]+ v[i-1]) for i in dp: print(i)pack2([2,3,4,5], [3,4,5,6], 8)结果为[0, 0, 0, 0, 0, 0, 0, 0, 0][0, 0, 3, 3, 6, 6, 9, 9, 12][0, 0, 3, 4, 6, 7, 9, 10, 12][0, 0, 3, 4, 6, 7, 9, 10, 12][0, 0, 3, 4, 6, 7, 9, 10, 12]同样可以优化空间复杂度 ，只需要把逆序改成顺序 即可。def pack2(w, v, C):

dp = [0 for _ in range(c+1)] for i in range(1, len(w)+1): for j in (range(1, c+1)): if w[i-1] <= j: dp[j] = max(dp[j], dp[j-w[i-1]]+v[i-1]) return dp[c]3 变形：多重背包问题，给定数量的物体，第⼀个是1个物体，第⼆个是⽆限物体，这个是介于之间，给定物体数⽬⽅法1：再多加个循环试⼀下k个物体的价值, 这次直接上优化完的⼀维数组的def pack3(w, v, s, c): dp = [0 for _ in range(c+1)] for i in range(1, len(w)+1): for j in reversed(range(1, c+1)): for k in range(s[i-1] + 1): if k*w[i-1] <= j: dp[j] = max(dp[j], dp[j-k*w[i-1]]+k*v[i-1]) return dp[c]⽅法2：想象加⼊物体数量为4个我们直接在 w= [2,3,4,5] v = [3,4,5,6] s(个数)=[1,1,1,3] 如果我们直接把4个物体分成3个1个物体，就可以直接转变成0，1问题 。 w变成[2,3,4,5,5,5], v变成[3,4,5,6,6,6] 这就完全变成了0，1问题。 但是如果物体个数太多这样复杂度⾼，我们有更好的划分⽅法。 ⽐如13 我们可以划分为1+2+4+6，利⽤这个划分，原来需要划分为n个1，现在只需要log n 个组 了def pack3(w, v, s, c): for i in range(len(s)): k = 1 s_value = s[i] while k<=s_value: (k*w[i]) (k*v[i]) s_value -= k k *= 2 if s_value>0: (s_value*w[i]) (s_value*v[i])

#前⾯是划分，后⾯是0，1背包 dp = [0 for _ in range(c+1)] for i in range(1, len(w2)+1): for j in reversed(range(1, c+1)): if w2[i-1] <= j: dp[j] = max(dp[j], dp[j-w2[i-1]]+v2[i-1]) return dp[c]4 背包问题变形：混合背包问题物品⼀共有三类：第⼀类物品只能⽤1次（01背包）；第⼆类物品可以⽤⽆限次（完全背包）；第三类物品最多只能⽤ sisi 次（多重背包）；si=−1 表⽰第 ii 种物品只能⽤1次；si=0 表⽰第 ii 种物品可以⽤⽆限次；si>0 表⽰第 ii 种物品可以使⽤ si 次；def pack4(w, v, c, s): w2 = [] v2 = [] s2 = [] for i in range(len(s)): if s[i] == 0 or s[i] == -1: (w[i]) (v[i]) (s[i]) else: s_value = s[i] k = 1 while k <= s_value: (k*w[i]) (k*v[i]) (s[i]) s_value -= k k *= 2 if s_value> 0: (s_value*w[i]) (s_value*v[i]) (s[i]) #上⾯把si>0的背包拆分了（变成0，1背包）下⾯分成0，1背包和⽆限背包两种 dp = [0 for _ in range(c+1)] for i in range(1, len(w2)+1): if s2[i-1] == 0: for j in (range(1, c+1)): if j-w2[i-1]>=0: dp[j] = max(dp[j], dp[j-w2[i-1]]+v2[i-1]) else: # print('i',i) for j in reversed(range(1, c+1)): if j-w2[i-1]>=0: # print('k', k) dp[j] = max(dp[j], dp[j-w2[i-1]]+v2[i-1]) # print('dp['+str(j)+']', dp[j]) # print(dp) print(dp[c])5 背包问题变形：分组背包问题分组，组内只能选择⼀个def pack5(w, v, n, c): """ w: list[list, list,...] v: list[list, list,...] n:list 组内的长度 """ dp = [0 for _ in range(c+1)] for i in range(1, len(w)+1): for j in reversed(range(1, c+1)): for k in range(n_list[i-1]): #别的和0，1背包⼀样 就是这⾥枚举⼀下每个组内的值，在每个组内选出⼀个max值 if j-w[i-1][k] >= 0: # print(dp[j]) dp[j] = max(dp[j], dp[j-w[i-1][k]] + v[i-1][k]) # print(dp) print(dp[c])6 背包问题变形：⼆维费⽤背包问题在重量的基础上再加上⼀个体积约束

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

背包问题及其变型（python）

1. 0，1问题⼀个背包，往⾥装东西，重量w(weight)分别为为[2,3,4,5] 价值v(value)对应为[3,4,5,6] 如果你的容量为8,每个物品只有⼀个，求你能装⼊背包的最⼤价值我们可以⼀步⼀步来 ，先创建⼀个表格 (数组), 数组dp[i][j] i代表你只⽤前i个物体，j代表你的剩余容量，dp[i][j] 代表在此情况下可以得到的最⼤价值，先得到⼀个表格先填第⼀⾏(也就是假设现在你只有第⼀个物体), ⾸先第⼀个物体重量为2 剩余容量为1，剩余容量⼩于物体重量，则最⼤价值为0， 第⼆个数剩余容量=物体容量，可以拿 填上第⼀个物体的价值3 就这样填上第⼀⾏ ， 继续填第⼆⾏ 第⼆⾏代表的意义就是我们现在可以使⽤的有两个物体了，使⽤这两个物体能够得到的最⼤价值。这⼀共可以分为两种情况，⼀种是放第⼆个物体，⼀种是不放第⼆个物体，选择其中⼤的，转移⽅程为dp[i][j] = max(dp[ i - 1, j ], dp[ i - 1, j - w[ i ] ] + v [ i ] ) 这⾥解释下放第⼆个物体的式⼦，dp[ i-1, j - w[ i ] ]代表你把第⼆个物体的容量空出来时，能得到的最⼤价值， 再加上这个物体的价值。就这样填好所有的。则 表格中最后⼀个物体就是⾯对所有物体，剩余容量为C时能得到的最⼤价值了。def pack1(w, v, C): #每个东西只能选择⼀次 dp = [[0 for _ in range(C+1)] for _ in range(len(w)+1)] for i in range(1, len(w)+1): for j in range(1, C+1): if j < w[i-1]: #如果剩余容量不够新来的物体 直接等于之前的 dp[i][j] = dp[i-1][j] else: dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]]+ v[i-1]) return dp[len(w)][c]这个是得到的dp结果观察发现，可以对它的空间复杂度进⾏优化，我们可以⽤⼀维数组只保存最后⼀⾏, 代码如下def pack1(w, v, c): #它是先得到第⼀⾏的值，存到dp中，然后再直接⽤dp相当于就是上⼀⾏的值，所以下⾯必须⽤逆序 #否则dp[j-w[i-1]]可能会⽤到你本⾏的值，从⼤到⼩就不会 dp = [0 for _ in range(c+1)] for i in range(1, len(w)+1): for j in reversed(range(1, c+1)):#这⾥必须⽤逆序 if w[i-1] <= j: dp[j] = max(dp[j], dp[j-w[i-1]]+v[i-1]) return dp[c]2 背包问题变形：完全背包问题还是原来的问题，上次是每个物体只能⽤1次，现在改成⽆限次，转移⽅程只需要修改⼀点即可dp[i][j] = max(dp[ i - 1, j ], dp[ i, j - w[ i ]] + v [ i ] ) 只需要把后⾯的i-1 -> i 即可def pack2(w, v, C): #每个东西能选择多次 完全背包问题 dp = [[0 for _ in range(C+1)] for _ in range(len(w)+1)] for i in range(1, len(w)+1): for j in range(1, C+1): if j < w[i-1]: dp[i][j] = dp[i-1][j] else: dp[i][j] = max(dp[i-1][j], dp[i][j-w[i-1]]+ v[i-1]) for i in dp: print(i)pack2([2,3,4,5], [3,4,5,6], 8)结果为[0, 0, 0, 0, 0, 0, 0, 0, 0][0, 0, 3, 3, 6, 6, 9, 9, 12][0, 0, 3, 4, 6, 7, 9, 10, 12][0, 0, 3, 4, 6, 7, 9, 10, 12][0, 0, 3, 4, 6, 7, 9, 10, 12]同样可以优化空间复杂度 ，只需要把逆序改成顺序 即可。def pack2(w, v, C):

dp = [0 for _ in range(c+1)] for i in range(1, len(w)+1): for j in (range(1, c+1)): if w[i-1] <= j: dp[j] = max(dp[j], dp[j-w[i-1]]+v[i-1]) return dp[c]3 变形：多重背包问题，给定数量的物体，第⼀个是1个物体，第⼆个是⽆限物体，这个是介于之间，给定物体数⽬⽅法1：再多加个循环试⼀下k个物体的价值, 这次直接上优化完的⼀维数组的def pack3(w, v, s, c): dp = [0 for _ in range(c+1)] for i in range(1, len(w)+1): for j in reversed(range(1, c+1)): for k in range(s[i-1] + 1): if k*w[i-1] <= j: dp[j] = max(dp[j], dp[j-k*w[i-1]]+k*v[i-1]) return dp[c]⽅法2：想象加⼊物体数量为4个我们直接在 w= [2,3,4,5] v = [3,4,5,6] s(个数)=[1,1,1,3] 如果我们直接把4个物体分成3个1个物体，就可以直接转变成0，1问题 。 w变成[2,3,4,5,5,5], v变成[3,4,5,6,6,6] 这就完全变成了0，1问题。 但是如果物体个数太多这样复杂度⾼，我们有更好的划分⽅法。 ⽐如13 我们可以划分为1+2+4+6，利⽤这个划分，原来需要划分为n个1，现在只需要log n 个组 了def pack3(w, v, s, c): for i in range(len(s)): k = 1 s_value = s[i] while k<=s_value: (k*w[i]) (k*v[i]) s_value -= k k *= 2 if s_value>0: (s_value*w[i]) (s_value*v[i])

#前⾯是划分，后⾯是0，1背包 dp = [0 for _ in range(c+1)] for i in range(1, len(w2)+1): for j in reversed(range(1, c+1)): if w2[i-1] <= j: dp[j] = max(dp[j], dp[j-w2[i-1]]+v2[i-1]) return dp[c]4 背包问题变形：混合背包问题物品⼀共有三类：第⼀类物品只能⽤1次（01背包）；第⼆类物品可以⽤⽆限次（完全背包）；第三类物品最多只能⽤ sisi 次（多重背包）；si=−1 表⽰第 ii 种物品只能⽤1次；si=0 表⽰第 ii 种物品可以⽤⽆限次；si>0 表⽰第 ii 种物品可以使⽤ si 次；def pack4(w, v, c, s): w2 = [] v2 = [] s2 = [] for i in range(len(s)): if s[i] == 0 or s[i] == -1: (w[i]) (v[i]) (s[i]) else: s_value = s[i] k = 1 while k <= s_value: (k*w[i]) (k*v[i]) (s[i]) s_value -= k k *= 2 if s_value> 0: (s_value*w[i]) (s_value*v[i]) (s[i]) #上⾯把si>0的背包拆分了（变成0，1背包）下⾯分成0，1背包和⽆限背包两种 dp = [0 for _ in range(c+1)] for i in range(1, len(w2)+1): if s2[i-1] == 0: for j in (range(1, c+1)): if j-w2[i-1]>=0: dp[j] = max(dp[j], dp[j-w2[i-1]]+v2[i-1]) else: # print('i',i) for j in reversed(range(1, c+1)): if j-w2[i-1]>=0: # print('k', k) dp[j] = max(dp[j], dp[j-w2[i-1]]+v2[i-1]) # print('dp['+str(j)+']', dp[j]) # print(dp) print(dp[c])5 背包问题变形：分组背包问题分组，组内只能选择⼀个def pack5(w, v, n, c): """ w: list[list, list,...] v: list[list, list,...] n:list 组内的长度 """ dp = [0 for _ in range(c+1)] for i in range(1, len(w)+1): for j in reversed(range(1, c+1)): for k in range(n_list[i-1]): #别的和0，1背包⼀样 就是这⾥枚举⼀下每个组内的值，在每个组内选出⼀个max值 if j-w[i-1][k] >= 0: # print(dp[j]) dp[j] = max(dp[j], dp[j-w[i-1][k]] + v[i-1][k]) # print(dp) print(dp[c])6 背包问题变形：⼆维费⽤背包问题在重量的基础上再加上⼀个体积约束