Python Greedy Algorithm

Question

I am writing a greedy algorithm (Python 3.x.x) for a 'jewel heist'. Given a series of jewels and values, the program grabs the most valuable jewel that it can fit in it's bag without going over the bag weight limit. I've got three test cases here, and it works perfectly for two of them.

Each test case is written in the same way: first line is the bag weight limit, all lines following are tuples(weight, value).

Sample Case 1 (works):

10
3 4
2 3
1 1

Sample Case 2 (doesn't work):

575
125 3000
50 100
500 6000
25 30

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 set_weight(weight):
    bag_weight = weight
    return bag_weight

def jewel_list(lines):
    jewels = []
    for item in lines:
        jewels.append(item.split())
    jewels = sorted(jewels, reverse= True)
    jewel_dict = {}
    for item in jewels:
        jewel_dict[item[1]] = item[0]
    return jewel_dict

def greedy_grab(weight_max, jewels):
    #first, we get a list of values
    values = []
    weights = []
    for keys in jewels:
        weights.append(jewels[keys])
    for item in jewels.keys():
        values.append(item)
    values = sorted(values, reverse= True)
    #then, we start working
    max = int(weight_max)
    running = 0
    i = 0
    grabbed_list = []
    string = ''
    total_haul = 0
    # pick the most valuable item first. Pick as many of them as you can.            
    # Then, the next, all the way through.
    while running < max:
        next_add = int(jewels[values[i]])
        if (running + next_add) > max:
            i += 1
        else:
            running += next_add
            grabbed_list.append(values[i])
    for item in grabbed_list:
        total_haul += int(item)
    string = "The greedy approach would steal $" + str(total_haul) + " of  
             jewels."
    return string

infile = "JT_test2.txt"
lines = take_input(infile)
#set the bag weight with the first line from the input
bag_max = set_weight(lines[0])
#once we set bag weight, we don't need it anymore
lines.pop(0)

#generate a list of jewels in a dictionary by weight, value
value_list = jewel_list(lines)
#run the greedy approach
print(greedy_grab(bag_max, value_list))

Does anyone have any clues why it wouldn't work for case 2? Your help is greatly appreciated. EDIT: The expected outcome for case 2 is $6130. I seem to get $6090.

Answer 1

Your dictionary keys are strings, not integers so they are sorted like string when you try to sort them. So you would get:

['6000', '3000', '30', '100']

instead wanted:

['6000', '3000', '100', '30']

Change this function to be like this and to have integer keys:

def jewel_list(lines):
    jewels = []
    for item in lines:
        jewels.append(item.split())
    jewels = sorted(jewels, reverse= True)
    jewel_dict = {}
    for item in jewels:
        jewel_dict[int(item[1])] = item[0]  # changed line
    return jewel_dict

When you change this it will give you:

The greedy approach would steal $6130 of jewels.

Answer 2

In [237]: %paste
def greedy(infilepath):
  with open(infilepath) as infile:
    capacity = int(infile.readline().strip())
    items = [map(int, line.strip().split()) for line in infile]

  bag = []
  items.sort(key=operator.itemgetter(0))
  while capacity and items:
    if items[-1][0] <= capacity:
      bag.append(items[-1])
      capacity -= items[-1][0]
    items.pop()
  return bag

## -- End pasted text --

In [238]: sum(map(operator.itemgetter(1), greedy("JT_test1.txt")))
Out[238]: 8

In [239]: sum(map(operator.itemgetter(1), greedy("JT_test2.txt")))
Out[239]: 6130

Answer 3

I think in this piece of code i has to be incremented on the else side too

while running < max:
  next_add = int(jewels[values[i]])
  if (running + next_add) > max:
    i += 1
  else:
    running += next_add
    grabbed_list.append(values[i])
    i += 1 #here

this and @iblazevic's answer explains why it behaves this way