Python贪婪算法

Question

我正在为'珠宝抢劫'写一个贪婪算法（Python 3.x.x）。鉴于一系列的珠宝和价值观，该计划抓住了它可以装入其包里的最有价值的宝石，而不会超过包重量限制。我在这里有三个测试用例，并且它对其中两个非常有用。

每个测试用例都是用相同的方式写的：第一行是行李重量限制，下面的所有行都是元组（重量，值）。

样本案例1（作品）：

10 
3 4 
2 3 
1 1 

样本案例2（不工作）：

575 
125 3000 
50 100 
500 6000 
25 30 

代码：

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

没有人有任何线索，为什么它不适用于情况2？非常感谢您的帮助。 编辑：情况2的预期结果是$ 6130。我似乎得到6090美元。

Answer 1

您的字典键是字符串，而不是整数，所以当您尝试对它们进行排序时，它们按字符串排序。所以，你会得到：

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

，而不是想：

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

更改此功能是这样的，并具有整数键：

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 

当你改变这一点，会给你：

The greedy approach would steal $6130 of jewels. 

Answer 2

我想我n这个代码段i对其他方递增太

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 

这一点，并@ iblazevic的回答解释了为什么它的行为这样

Answer 3

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