我正在尝试用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 类型的斗争。这次似乎在断绝关系,但我不确定修复它的方法是什么。任何帮助将不胜感激。当我看到它时,我只知道这将是一个简单的修复......
编辑:这与我的列表如何排序有关。我有一个列表列表,反向排序。但是,如果 item[0] 和 item2[0] 之间有联系,我需要按 item[1] 排序。我不知道怎么回事。
在第二种情况下,sorted(jewels_list, reverse=True)
返回 [(150, 151), (150, 150)],因此您的算法选择了相等的宝石中最重的宝石。您应该按值降序和权重升序排序,以获得所需的内容。