-3

我有这个问题：“给定 n 个重量从 1 公斤到 10 公斤不等的物品，你如何在最少数量的袋子之间分配它们，知道每个袋子可能不超过 10 公斤。”。

我尝试通过将物品从最重到最轻分类来解决这个问题，如果它们合适则将它们放入一个袋子中，如果它们不合适则创建一个新袋子。如果是这种情况，则从剩余物品的最重到最轻重新开始。这是我的代码：

list_of_items=raw_input("Input the items' weights (separated by spaces): ").split()

for i in range(len(list_of_items)):
        list_of_items[i]=int(list_of_items[i])

list_of_items.sort()
list_of_items.reverse()

while list_of_items[0]>=10:
        list_of_items=raw_input("You have input an item wheighing over 10kg: ").split()
        for i in range(len(list_of_items)):
                list_of_items[i]=int(list_of_items[i])

        list_of_items.sort()
        list_of_items.reverse()

set_of_bags=[] #In this list we'll store the bags

while(len(list_of_items)!=0):

        weight=0
        bag=[] #creates a new bag

        for item in list_of_items: #cycle copies items to bag
                if item+weight<=10:
                        bag.append(item)
                        weight+=item
        set_of_bags.append(bag) #adds bag to set_of_bags

        for item in bag: #deletes the items that have been put in set_of_bags from original list
                list_of_items.remove(item)

# output
n=0
for bag in set_of_bags:
        n+=1
        weight=0
        for j in bag:
                weight += j
        print "bag #"+str(n), bag, "=>", weight, "kg."

我相信这给出了正确的答案，但我不知道如何证明它。有什么帮助吗？

4

2 回答 2

1

当然，这不是最优的。一般来说，如果你有一个非平凡的算法对某物进行排序，然后使用“贪婪方法”，即选择最小或最大的东西，而你不确定为什么这是正确的，那么它可能是错误的。特别是如果您有整数的优化问题。

如果你有 ，3, 3, 3, 3, 4, 4那么你的算法最终将使用三个袋子而不是两个。

你的算法：

Bag 1: 4, 4
Bag 2: 3, 3, 3
Bag 3: 3

最佳：

Bag 1: 4, 3, 3
Bag 2: 4, 3, 3

现在，只是为了表明其他一些启发式方法也是错误的，看看这个例子3, 3, 4, 6, 7, 7：如果你从最低到最高并放入3, 3, 4一个袋子，你最终会得到四个袋子而不是三个。同样的例子表明，仅仅因为你可以装满一个袋子并不意味着你应该这样做。（但是，如果您只有两个组合在一起的物品，例如7和3，那么您可以将它们放在一个袋子中并完全忘记它们。）

最后，看3, 3, 3, 3, 4, 4, 4, 4。如果你从最低点开始，你会得到四个袋子：

Bag 1: 3 3 3
Bag 2: 3 4
Bag 3: 4 4
Bag 4: 4

如果你从最高处走，你会得到四个袋子：

Bag 1: 4 4
Bag 2: 4 4
Bag 3: 3 3 3
Bag 4: 3

但是，您可以获得三个袋子：

Bag 1: 4 3 3
Bag 2: 4 3 3
Bag 3: 4 4

这是你可以做的（我省略了证明）：

  • 如果您有 10 个，请将其放在单独的袋子中。首先处理所有10s。
  • 如果你有一个 9，如果可能的话，把它和一个 1 放在一个袋子里，或者单独放在一个袋子里。在继续之前处理所有 9。
  • 如果你有一个 8，如果可能的话，把它和一个 2 放在一个袋子里，或者如果可能的话，把它和两个 1 放在一个袋子里，或者如果可能的话，把它和一个 1 放在一个袋子里，或者单独放在一个袋子里。在继续之前处理所有 8。
  • 如果你有一个 7，把它和一个 3 放在一个袋子里，如果没有，把一个 2 和一个 1 放在一个袋子里，如果没有，把它放在一个 2 里，或者如果没有，把你剩下的 1 放在一个袋子里。在继续之前处理所有 7。
  • 如果你有 6，就把 if 和 4 放在一起。如果没有，这里就很棘手了......
  • 此时你只剩下6s、5s、3s、2s、1s。现在，1 并不重要。您可以消除它们，找到最佳解决方案，然后将它们添加回来。此外，如果您至少有两个 5，请将它们加在一起并制作一个袋子（也很容易证明）。因此，你有 6s、3s、2s，最多有一个 5。如果你有一个 5，那么如果可能的话，它必须与 3 一起使用，然后与 2 或你剩下的任何 1 一起使用。如果你没有 3，那么你的 5 必须和你剩下的 2 一样多，然后是 1。
  • 所以现在我们还剩下 6s、3s 和 2s。现在它就像一个简单的游戏。你只有 2s 和 3s，这很重要。每个“6”允许您取一个“3”或两个“2”。在你用完 6 之后，你可以拿 5 个 2，或者一个 3 和三个 2，或者两个 3 和两个 2，或者三个 3。现在您可以使用动态规划来找到最佳解决方案。例如，让d[i, j, k]为i2s、j3s 和k6s 的最小袋数。可能有更好的解决方案。
于 2013-10-08T19:18:41.757 回答
0

我认为这很接近，但我认为您没有考虑可能出现故障的重量，看起来如果您有 9 公斤、5 公斤、1 公斤的物品。它会添加 9 公斤的物品，看到 5 公斤的东西太多并跳到下一个袋子，即使 1 公斤的物品适合。

我并不像大多数人那样了解 Python 优化，但我认为最快的会是。

获取原始值，（10KG、5KG、8KG、2KG、2KG、1KG、10KG、9KG）；分类/索引重量（10KG:2、9KG:1、8KG:1、5KG:1、2KG:2、1KG:1）

首先开始用最重的值填充袋子，如果重量超过尝试添加下一个最大的索引，直到袋子在值索引的末尾是 A：满或 B：。

根据值的数量...实际上可能更快地向后搜索值索引并针对下一个最高值进行测试，这样您就不必为较大的项目迭代尽可能多的值。（比如10KG测1KG看不行，9KG测1KG看行，也测2KG看不行，所以取1KG为最佳值，这还是只有从 8, 5, 2 ,1) 开始需要 2 次迭代，而不是 4 次。

我希望这是有道理的。

于 2013-10-08T19:01:37.297 回答