贪婪算法 - 背包谜题

Question

我试图用Python 3.x中的贪婪算法解决背包问题。下面是我的代码，以及我用来测试它的示例。每个样品的情况下在形式线[0] =最大重量，线[1：]在形式（重量值。）

样品壳体1 成功：

575 
125 3000 
50 100 
500 6000 
25 30 

预期$ 6130得到$ 6130。

样本案例2 不成功：

1500 
151 150 
150 150 

预计$ 1500，得到了$ 1350

代码：

def take_input(infile): 
    f_open = open(infile, 'r') 
    lines = [] 
    for line in f_open: 
     lines.append(line.strip()) 
    f_open.close() 
    return lines 

def create_list(jewel_lines): 
    #turns the jewels into a list of lists 
    jewels_list = [] 
    for x in jewel_lines: 
     weight = x.split()[0] 
     value = x.split()[1] 
     jewels_list.append((int(value), int(weight))) 
    jewels_list = sorted(jewels_list, reverse=True) 
    return jewels_list 

def greedy_grab(jewels_list, max_weight): 
    running = 0 
    i = 0 
    grabbed_list = [] 
    string = '' 
    total_haul = 0 
    #sort jewels list by value, since this is greedy 

    while running <= max_weight and i <= (len(jewels_list)-1): 
     #pick the most valuable item 
     to_add = int(jewels_list[i][1]) 
     if (running + to_add) > max_weight: 
      i += 1 
     else: 
      running += to_add 
      grabbed_list.append(jewels_list[i][0]) 
    for item in grabbed_list: 
     total_haul += int(item) 
    string = "The greedy approach would steal $" + str(total_haul) + " of jewels." +"It would use value " + str(grabbed_list) 
    return string 

#required setup of variables  
infile = "JT_test3.txt" 
given_input = take_input(infile) 
max_weight = int(given_input[0]) 
given_input.pop(0) 
jewels_list = create_list(given_input) 

#test lines 
print(jewels_list) 
print(greedy_grab(jewels_list, max_weight)) 

我最后一次有这样的错误，在我重写了程序，它是在int型的斗争。这一次它似乎在打破关系，但我不确定解决问题的方法是什么。任何帮助是极大的赞赏。我只是知道这将是一个简单的修复，当我看到它...

编辑：这必须是如何与我的列表如何排序。我有一个列表清单，反向排序。但是，如果项目[0]和项目2 [0]之间有联系，我需要按项目[1]排序。虽然我不知道。

Answer 1

在第二种情况下，sorted(jewels_list, reverse=True)返回[（150,151），（150,150）]，所以你的算法在同等重量的珠宝中选择了最重的珠宝。你应该按价值降序和按重量升序排序，以得到你所期望的。