貪婪算法 - 揹包謎題

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）]，所以你的算法在同等重量的珠寶中選擇了最重的珠寶。你應該按價值降序和按重量升序排序，以得到你所期望的。