Python贪心算法

Question

我正在为“珠宝抢劫案”编写贪婪算法(Python 3.x.x)。给定一系列珠宝和值(value)，该程序会在不超过包重量限制的情况下抓取它可以放入包中的最有值(value)的珠宝。我这里有三个测试用例，它非常适合其中两个。

每个测试用例的写法都是一样的:第一行是包的重量限制，后面所有的行都是tuples(weight, value)。

示例案例 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.