python - 使用回溯在python中实现0/1背包问题

Question

我想显示给定 Maxweigth 和所选项目索引的最大值。
我还想计算执行期间发生的递归调用次数。

• 使用 generate 函数生成随机权重和值列表。
  
• vsol[] 选择了项目索引的最终列表
• temp[] 保存临时选择的索引
• values[] 将保存项目值的数组
• weights[] 将保存项目的权重数组
• Knapsack() 之后的解决方案将保存给定重量（Knapsack() 的第二个参数） 输入的最大值：values[] = [60,100,120], weights[10,20,30], maxWeigth = 50预期输出: 220 [1,2]输出站点: 0 [] 对于每个输入选定项索引
  
  

import random
import copy

weights = []
values = []
temp = []
vsol = []
isSol = False
solution = 0
def Knapsack(i,max,value):
    for k in range(i,len(values)):
        if max > 0:
            if weights[k] <= max:
                temp.append(k);
                if (value+values[k] >= solution):
                    solution = value+values[k];
                    isSol = True
            if (k+1)<n:
                Knapsack(k+1,max-weight[k],value+values[k])
            else:
                if isSol == True:
                    vsol = []
                    vsol = copy.deepcopy(temp)
                    temp = []
                    isSol = False
                else:
                    temp = []
                    return
        else:
            if isSol == True:
                vsol = []
                vsol = copy.deepcopy(temp)
                temp = []
                isSol = False
            else:
                temp = []
                return
    
    

def generator(n):
    l = [];
    for i in range(n):
        l.append(random.randint(1,100))
    return l    
def main():
    n = 10 #number of random numbers
    weights = generator(n);
    values = generator(n);
    Knapsack(0,10,0)
    print(solution,vsol)
    
main()

我尝试将临时列表深度复制到 vsol[]。

标签： pythonalgorithmanalysisbacktrackingknapsack-problem

Answer 1

import sys
import math
sys.setrecursionlimit(10**8)

c = 0
def knapSack(mW,w,v,n):
    # counter how many time recursive function is called.
    global c
    c += 1
    
    if(mW == 0 or n == 0):
        return [0,[]]
        
    if(w[n-1] > mW):
        return knapSack(mW,w,v,n-1)
        
    set1 = knapSack(mW-w[n-1],w,v,n-1)
    set2 = knapSack(mW,w,v,n-1)
    
    if(set1[0]+v[n-1] > set2[0]):
        set1[1].append(n-1)
        set1[0] += v[n-1]
        return set1
    else:
        return set2
        
val = [160, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print("Knapsack Max & list:",knapSack(W, wt, val, n))
print("Total Recursive Steps: ",c)
    

Python 导师：将来使用这个模拟器来了解正在发生的事情。