蛮力算法奶牛运输的问题

Question

我正在研究优化问题，但我被困在一个家庭作业问题上。我必须编写一个蛮力算法来最大限度地减少宇宙飞船旅行的次数。问题是：外星人创造了一种新型的牛，现在他们想用最少的旅行次数把它运回来。每次行程的最大值为 10 吨。

该练习提供了一些东西，例如此算法来获取列表的所有可能分区：

# From codereview.stackexchange.com                    
def partitions(set_):
if not set_:
yield []
return
for i in range(2**len(set_)//2):
parts = [set(), set()]
for item in set_:
parts[i&1].add(item)
i >>= 1
for b in partitions(parts[1]):
yield [parts[0]]+b
def get_partitions(set_):
for partition in partitions(set_):
yield [list(elt) for elt in partition]

输入是奶牛的字典，就像这样：cows = {'Jesse'： 6，'Maybel'： 3， 'Callie'： 2， 'Maggie'： 5}，键是奶牛的名字，值是奶牛的重量(以吨为单位(。

输出必须是列表列表，其中每个内部列表代表一个行程，如下所示： [["杰西"、"凯莉"]、["梅贝尔"、"玛姬]]

我的问题是：如何使用 get_partitions(( 实现此算法？DFS是解决这个问题的好方法吗？

我已经尝试了很多方法，但是我在stackoverflow上找到的两种方法似乎更接近答案是：

• 使用 get_partitions(( 函数获取所有可能的组合，并选择列表中所有服从limit = 10的组合。就像我在这里看到的：为什么这种蛮力算法会产生不正确的结果？但它不起作用，因为它返回了一个空列表。

• 然后我尝试了深度优先搜索，就像我在这里看到的那样，有一些变化：如何从所有蛮力组合中找到最佳解决方案？ 并且列表尚未返回正确答案。

这是我从正确答案中得到的最接近的结果。首先，我使用 get_partitions 生成所有可能的分区，然后将分区过滤到一个名为"可能"的列表，其中只有带有limit <= 10的行程，以及行程中是否包含所有奶牛(以排除那些只有一个或两个奶牛名称的分区(。

def brute_force_cow_transport(cows,limit=10):
"""
Finds the allocation of cows that minimizes the number of spaceship trips
via brute force.  The brute force algorithm should follow the following method:
1. Enumerate all possible ways that the cows can be divided into separate trips
Use the given get_partitions function in ps1_partition.py to help you!
2. Select the allocation that minimizes the number of trips without making any trip
that does not obey the weight limitation
Does not mutate the given dictionary of cows.
Parameters:
cows - a dictionary of name (string), weight (int) pairs
limit - weight limit of the spaceship (an int)
Returns:
A list of lists, with each inner list containing the names of cows
transported on a particular trip and the overall list containing all the
trips
"""
possible_combinations = []
for partition in get_partitions(cows.keys()):
possible_combinations.append(partition)
possible_combinations.sort(key=len)
def _is_valid_trip(cows, trip):
valid = False
for cow_name in cows:
if cow_name in trip:
valid = True
else:
valid = False
return valid
possibles = []
for partition in possible_combinations:
trips = []
for trip in partition:
total = sum([cows.get(cow) for cow in trip])
if total <= limit and _is_valid_trip(cows.keys(), trip):
trips.append(trip)
possibles.append(trips)
all_possibilities = [possibility for possibility in possibles if possibility != []]
return min(all_possibilities)

我的测试用例仍然给出：

AssertionError: Lists differ: [['Callie', 'Maggie']] != [['Jesse', 'Callie'], ['Maybel', 'Maggie']]
First differing element 0:
['Callie', 'Maggie']
['Jesse', 'Callie']

Second list contains 1 additional elements.
First extra element 1:
['Maybel', 'Maggie']
- [['Callie', 'Maggie']]
+ [['Jesse', 'Callie'], ['Maybel', 'Maggie']]
----------------------------------------------------------------------
Ran 5 tests in 0.009s
FAILED (failures=1)

Answer 1

这是我

从正确答案中得到的最接近的答案。首先，我使用 get_partitions 生成所有可能的分区，然后将分区过滤到一个名为"可能"的列表，其中只有限制为 <= 10 的行程，并且行程中是否包含所有奶牛(以排除那些只有一个或两个奶牛名称的分区(。

这是正确的想法，除了最后一条语句，根据定义，集合的分区将恰好包含集合的所有元素一次。问题是您正在从行程而不是分区构建列表，没有必要这样做，因为您已经在possible_combinations中生成了完整的分区集，您需要做的就是删除那些包含超过权重限制的行程的分区，这会给您留下这样的内容：

def brute_force_cow_transport(cows, limit):
## Generate set of partitions
possible_combinations = []
for partition in get_partitions(cows.keys()):
possible_combinations.append(partition)
possible_combinations.sort(key=len)
valid_combinations = possible_combinations[:] ## or list.copy() if using python 3.3+
## Remove invalid partitions
for partition in possible_combinations:
for trip in partition:
total = sum([cows.get(cow) for cow in trip])
if total > limit:
valid_combinations.remove(partition)
break
## Return valid partition of minimum length
return min(valid_combinations, key=len)

在这里，由于我们正在迭代分区，因此我们首先复制分区列表，以便我们可以删除包含超出限制的行程的分区，然后返回最小长度列表作为解决方案。有一些简单的方法可以提高这种性能，但它们留给读者作为练习。