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

有人知道为什么第二种情况不起作用吗？非常感谢你的帮助。 编辑：第二种情况的预期结果是$6130。但我似乎只得到了$6090。

- idalsin

---

在case2中预期的输出是什么？而实际观察到的输出又是什么？ - inspectorG4dget

预期：$6130 实际：$6090 - idalsin

你应该将那些信息编辑到你的帖子中，这样每个人都可以看到。另外，观察到了什么结果？ - inspectorG4dget

另外，请修正您代码中的缩进。请粘贴您的代码，然后点击文本框上方的“{}”按钮来完成操作。 - inspectorG4dget

听起来像是背包问题。 - Eric

Answer 1

您的字典键是字符串，而不是整数，因此在尝试进行排序时它们会像字符串一样进行排序。所以您将得到：

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

instead wanted:

['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.

- iblazevic

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

- inspectorG4dget

Answer 3

我认为在这段代码中，i 在 else 部分也必须被递增。

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的回答解释了为什么它会表现出这种方式

- titus

---

在 while 循环的那个部分递增它，这样做会阻止它成为贪心算法吗？我希望它能一直选择那个高价值的珠宝，直到满足第一个 if 语句，然后迭代到列表中的下一个。我认为你的方法只允许我选择那个珠宝一次，如果我理解正确的话。 - idalsin

哦，好的，我以为你只能选择一次。 - titus

你可以这样做：running += (max-running) / value*value。 - titus