背包问题追踪解

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

背包问题追踪解混合背包问题通⽤处理如下，我们以通⽤状态⽅式处理解空间的追踪：def pack_01_and_complete_and_multiple_Bottom_up(N,V,C,W,M): list = ((N+1,V+1),dtype=int) for i in range(1,N+1): for j in range(0,V+1): t = min(j // C[i-1],M[i-1]) result = -1000 for k in range(t+1): A = list[i-1,j-k*C[i-1]] + k*W[i-1] if A > result: result = A list[i,j] = result

return list[N,V]我们⽤G[i][v]来追踪解，这⾥⾯记录的是在i,v状态下取了多少件i物品def pack_01_and_complete_and_multiple_Bottom_up(N,V,C,W,M): list = ((N+1,V+1),dtype=int) G = ((N+1,V+1),dtype=int) for i in range(1,N+1): for j in range(0,V+1): t = min(j // C[i-1],M[i-1]) result = -1000 for k in range(t+1): A = list[i-1,j-k*C[i-1]] + k*W[i-1] if A > result: result = A G[i,j] = k list[i,j] = result

return list[N,V] ,G然后逆向搜索解空间得到PATHdef decode_G(G,N,V,W,C): i = N v = V while i > 0: print("Choose value {} : cost {}: how many {}".format(W[i-1],C[i-1],G[i,v])) v -= G[i,v]*C[i-1] i -= 1运⾏结果：pythonN = 8V = 20C = [11,2,3,9,13,6,7,5]W = [1,2,5,7,5,11,6,14]M = [10,2,9,1,19,3,4,1]value,path = pack_01_and_complete_and_multiple_Bottom_up(N,V,C,W,M)

print valuedecode_G(path,N,V,W,C)41Choose value 14 : cost 5: how many 1Choose value 6 : cost 7: how many 0Choose value 11 : cost 6: how many 2Choose value 5 : cost 13: how many 0Choose value 7 : cost 9: how many 0Choose value 5 : cost 3: how many 1Choose value 2 : cost 2: how many 0Choose value 1 : cost 11: how many 0选与不选，就是01问题的追踪：import numpy as npdef pack_01_track_solution_Bottom_up(N,V,C,W): track_solution = ((N+1,V+1),dtype = int) list =[0]*(V+1) for i in range(1,N+1): for v in range(V,C[i-1]-1,-1): if list[v] < list[v-C[i-1]] + W[i-1]: list[v] = list[v-C[i-1]] + W[i-1] track_solution[i,v] = 1# else:# track_solution[i,v] = 0

return list[V],track_solutiondef track_solution(G,N,V,W,C): i = N v = V while i > 0: print("Choose value {} : cost {}: how many {}".format(W[i-1],C[i-1],G[i,v])) v -= G[i,v]*C[i-1] i -= 1⽆限数量，完全背包问题，标记函数：def pack_complete_track_solution_Bottom_up(N,V,C,W): track_solution = ((N+1,V+1),dtype = int) track_solution[1:,1:] =-1 list =[0]*(V+1) for i in range(1,N+1): for v in range(C[i-1],V+1): if list[v] <= list[v-C[i-1]] + W[i-1]: list[v] = list[v-C[i-1]] + W[i-1] track_solution[i,v] = i else: track_solution[i,v] = track_solution[i-1,v]

return list[V],track_solutiondef track_solution_standard(G,N,V,W,C): i = N v = V while G[i,v] !=0:

i = G[i,v] m = 0 while G[i,v] == i:#

在v的⽅向上搜索 m +=1 v -=C[i-1]

print("Choose value {} : cost {}: how many {}".format(W[i-1],C[i-1],m))

while G[i,v] == -1:#

在i的⽅向上搜索 i -=1#%%N = 8V = 30C = [11,2,3,9,13,6,15,7,19]W = [1,2,5,7,5,11,6,14]value,path = pack_complete_track_solution_Bottom_up(N,V,C,W)

print valueprint pathtrack_solution_standard(path,N,V,W,C)

58[[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [ 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1] [ 0 -1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2] [ 0 -1 -1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3] [ 0 -1 -1 -1 -1 -1 -1 -1 -1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3] [ 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3] [ 0 -1 -1 -1 -1 -1 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6] [ 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6] [ 0 -1 -1 -1 -1 -1 -1 8 8 8 8 8 -1 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8]]8Choose value 14 : cost 7: how many 42Choose value 2 : cost 2: how many 1标记函数⾸先是得到标记列表，⼜叫映射表，追踪解的过程实际就是⼀个双指针模型的搜索，在这⾥对应的就是i,v怎么收缩，编码过程，先把表画出来，确定双针移动的⽅式，最后确定边界条件，也就是循环的条件。

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

背包问题追踪解混合背包问题通⽤处理如下，我们以通⽤状态⽅式处理解空间的追踪：def pack_01_and_complete_and_multiple_Bottom_up(N,V,C,W,M): list = ((N+1,V+1),dtype=int) for i in range(1,N+1): for j in range(0,V+1): t = min(j // C[i-1],M[i-1]) result = -1000 for k in range(t+1): A = list[i-1,j-k*C[i-1]] + k*W[i-1] if A > result: result = A list[i,j] = result

return list[N,V]我们⽤G[i][v]来追踪解，这⾥⾯记录的是在i,v状态下取了多少件i物品def pack_01_and_complete_and_multiple_Bottom_up(N,V,C,W,M): list = ((N+1,V+1),dtype=int) G = ((N+1,V+1),dtype=int) for i in range(1,N+1): for j in range(0,V+1): t = min(j // C[i-1],M[i-1]) result = -1000 for k in range(t+1): A = list[i-1,j-k*C[i-1]] + k*W[i-1] if A > result: result = A G[i,j] = k list[i,j] = result

return list[N,V] ,G然后逆向搜索解空间得到PATHdef decode_G(G,N,V,W,C): i = N v = V while i > 0: print("Choose value {} : cost {}: how many {}".format(W[i-1],C[i-1],G[i,v])) v -= G[i,v]*C[i-1] i -= 1运⾏结果：pythonN = 8V = 20C = [11,2,3,9,13,6,7,5]W = [1,2,5,7,5,11,6,14]M = [10,2,9,1,19,3,4,1]value,path = pack_01_and_complete_and_multiple_Bottom_up(N,V,C,W,M)

print valuedecode_G(path,N,V,W,C)41Choose value 14 : cost 5: how many 1Choose value 6 : cost 7: how many 0Choose value 11 : cost 6: how many 2Choose value 5 : cost 13: how many 0Choose value 7 : cost 9: how many 0Choose value 5 : cost 3: how many 1Choose value 2 : cost 2: how many 0Choose value 1 : cost 11: how many 0选与不选，就是01问题的追踪：import numpy as npdef pack_01_track_solution_Bottom_up(N,V,C,W): track_solution = ((N+1,V+1),dtype = int) list =[0]*(V+1) for i in range(1,N+1): for v in range(V,C[i-1]-1,-1): if list[v] < list[v-C[i-1]] + W[i-1]: list[v] = list[v-C[i-1]] + W[i-1] track_solution[i,v] = 1# else:# track_solution[i,v] = 0

return list[V],track_solutiondef track_solution(G,N,V,W,C): i = N v = V while i > 0: print("Choose value {} : cost {}: how many {}".format(W[i-1],C[i-1],G[i,v])) v -= G[i,v]*C[i-1] i -= 1⽆限数量，完全背包问题，标记函数：def pack_complete_track_solution_Bottom_up(N,V,C,W): track_solution = ((N+1,V+1),dtype = int) track_solution[1:,1:] =-1 list =[0]*(V+1) for i in range(1,N+1): for v in range(C[i-1],V+1): if list[v] <= list[v-C[i-1]] + W[i-1]: list[v] = list[v-C[i-1]] + W[i-1] track_solution[i,v] = i else: track_solution[i,v] = track_solution[i-1,v]

return list[V],track_solutiondef track_solution_standard(G,N,V,W,C): i = N v = V while G[i,v] !=0:

i = G[i,v] m = 0 while G[i,v] == i:#

在v的⽅向上搜索 m +=1 v -=C[i-1]

print("Choose value {} : cost {}: how many {}".format(W[i-1],C[i-1],m))

while G[i,v] == -1:#

在i的⽅向上搜索 i -=1#%%N = 8V = 30C = [11,2,3,9,13,6,15,7,19]W = [1,2,5,7,5,11,6,14]value,path = pack_complete_track_solution_Bottom_up(N,V,C,W)

print valueprint pathtrack_solution_standard(path,N,V,W,C)

58[[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [ 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1] [ 0 -1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2] [ 0 -1 -1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3] [ 0 -1 -1 -1 -1 -1 -1 -1 -1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3] [ 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3] [ 0 -1 -1 -1 -1 -1 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6] [ 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6] [ 0 -1 -1 -1 -1 -1 -1 8 8 8 8 8 -1 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8]]8Choose value 14 : cost 7: how many 42Choose value 2 : cost 2: how many 1标记函数⾸先是得到标记列表，⼜叫映射表，追踪解的过程实际就是⼀个双指针模型的搜索，在这⾥对应的就是i,v怎么收缩，编码过程，先把表画出来，确定双针移动的⽅式，最后确定边界条件，也就是循环的条件。