Greedy Algorithm- Knacksack Puzzle

Question

Я пытаюсь решить проблему Knapsack с жадным алгоритмом в 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. На этот раз, похоже, это разрыв связей, но я не уверен, как это исправить. Любая помощь приветствуется. Я просто знаю, что это будет простое исправление, когда я это вижу ...

EDIT: Это должно быть связано с тем, как сортируются мои списки. У меня есть список списков, отсортированных в обратном порядке. В случае связи между пунктом [0] и пунктом2 [0], мне нужно отсортировать по элементу [1]. Однако я не знаю, как это сделать.

Answer 1

Во втором случае sorted(jewels_list, reverse=True) возвращает [(150, 151), (150, 150)], поэтому ваш алгоритм выбирает самую тяжелую драгоценность среди равных весовых. Вы должны сортировать по значениям по убыванию и по весу по возрастанию, чтобы получить то, что вы ожидаете.