Greedy Algorithm- Knapsack Puzzle

Question

I am attempting to solve the Knapsack problem with a greedy algorithm in Python 3.x. Below is my code, and the sample cases I'm using to test it. Each sample case is in the form line[0] = max weight, line[1:] in form (weight, value.)

Sample case 1 successful:

575
125 3000
50 100
500 6000
25 30

Expected $6130, got $6130.

Sample case 2 not successful:

1500
151 150
150 150

Expected $1500, got $1350.

Code:

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))

The last time I had an error like this, before I rewrote the program, it was a struggle with int types. This time it seems to be in breaking ties, but I'm not sure what the way to fix it is. Any help is greatly appreciated. I just know this'll be a simple fix when I see it...

EDIT: this has to be something to do with how my lists are sorted. I have a list of lists, sorted in reverse. In case of a tie between item[0] and item2[0], though, I need to sort by item[1]. I don't know how though.

Answer 1

In second case, sorted(jewels_list, reverse=True) returns [(150, 151), (150, 150)], so your algoritm choses the heaviest jewel amongst equaly weghted ones. You should sort by value descending and by weight ascending to get what you expect.