0

我正在使用动态编程实现 0/1 背包问题。但是，当物品数量或麻袋容量太大时，我的算法无法完成，导致异常。这是一个简单的 DP 算法，它为项目编号创建一个 2D 矩阵。与容量。这是我的代码片段：

def solve_it(input_data):
    # Modify this code to run your optimization algorithm
    
    # parse the input
    lines = input_data.split('\n')

    firstLine = lines[0].split()
    item_count = int(firstLine[0])
    capacity = int(firstLine[1])

    
    vals=[]
    weights=[]

    for i in range(1, item_count+1):
        line = lines[i] 
        parts = line.split() 
        #items.append(Item(i-1, int(parts[0]), int(parts[1]))) 
        vals.append(int(parts[0])) 
        weights.append(int(parts[1])) 
    taken=[0 for i in range(len(weights))]    
    list=[[0 for j in range(capacity + 1)] for i in range(len(weights) + 1)]
    for item in range(len(weights)+1):             
        for wt in range(capacity + 1): 
            if item==0 or wt==0:
                list[item][wt]=0  
            elif weights[item-1]<=wt: 
                if (vals[item-1]+list[item-1][wt-weights[item-1]])>=list[item-1][wt]:  
                    list[item][wt]=vals[item-1]+list[item-1][wt-weights[item-1]] 
                else:  
                    list[item][wt]=list[item-1][wt] 
            else: 
                list[item][wt]=list[item-1][wt] 
    n=item_count
    w=capacity 
    while n>0: 
          if list[n][w]!=list[n-1][w]:
              taken[n-1]=1
              w=w-weights[n-1]
          n-=1    
                
    value=list[item_count][capacity]
    if capacity> sum(weights[:]):
        opt=0
    else:
        opt=1
        
    
    # prepare the solution in the specified output format
    output_data = str(value) + ' ' + str(opt) + '\n'
    output_data += ' '.join(map(str, taken))
    return output_data

有什么想法可以提高执行时间吗？

4

0 回答 0