0

我想返回元组，使它们的重量加起来达到 400，但也不应该有重复的类。

所以下面的最佳解决方案是（项目，重量<400，最大值，没有重复类，所以1a，1e，1g，1b）

#mytuple = (item, weight, value, class)
mytuple= (('map', 9, 150, 'a'), ('compass', 13, 35, 'a'), ('water', 153, 200, 'a'), ('sandwich', 50, 160, 'a'), ('glucose', 15, 60, 'e'), ('banana', 27, 60, 'g'), ('suntan cream', 11, 70, 'a'), ('waterproof trousers', 42, 70, 'e'), ('waterproof overclothes', 43, 75, 'a'), ('note-case', 22, 80, 'a'), ('sunglasses', 7, 20, 'b'), ('socks', 4, 50, 'a'))
4

2 回答 2

1

您可能要考虑使用集合或字典（以类为键），而不是元组的元组。它们更容易操作。

问题本身就是背包问题，这是计算机科学的经典部分，并且在整个互联网上都有详尽的记录。

最简单（但通常不准确）的解决方案是贪心算法，但由于这几乎可以肯定是一个家庭作业问题，因此您需要动态规划解决方案 - 因为这是动态规划的规范介绍。这是一个很好的概述，具有可读的伪代码和漂亮的表格。

于 2013-10-21T23:09:11.633 回答
0

以下是从列表中删除元素的方法：

>>> a = [1, 2, 3]
>>> a
[1, 2, 3]
>>> a.pop()  #remove & return the right-most element
3
>>> a
[1, 2]
>>> a.pop(0) #remove & return element at given index
1
>>> a
[2]

至于您的问题，它是装箱问题的变体，并且是 NP 难的。

于 2013-10-21T23:07:16.443 回答