饼干怪物问题：将所有数组元素减少到 0 的最小步数

Question

我正在研究饼干怪物问题：

饼干怪物有一张桌子，上面有一堆饼干，每堆都是一个正整数。饼干怪物必须以尽可能短的动作顺序吃掉这些饼干。每次移动都由饼干怪物选择一个整数组成，该整数必须是剩余堆大小之一。所选择的移动会从至少包含饼干的每一堆中移除饼干，并将所有较小的一堆保留为移动之前的状态。

此函数应计算并返回允许 Cookie Monster 吃掉这些饼干的最小移动次数。

桩	预期结果	（最佳动作）
[1,2,3,4,5,6]	3	[4,2,1]
[2、3、5、8、13、21、34、55、89]	5	[55,21,8,3,2]
[1、10、17、34、43、46]	5	[34,9,8,3,1]
[11、26、37、44、49、52、68、75、87、102]	6	[37、31、15、12、7、4]
[2**n for n in range (10)]	10	[512、256、128、64、32、16、8、4、2、1]

我得到这个提示：

对于给定的桩，您的函数应该循环遍历其可能的移动，并递归地解决将每个移动应用于桩所产生的新桩的问题。那么，桩的最佳解决方案就是这些子问题解决方案中的最佳解决方案加一。

我的想法是从列表的末尾开始，按降序向下移动。

到目前为止，这是我的代码：

piles=[11, 26, 37, 44, 49, 52, 68, 75,87, 102]
p=piles
n=len(piles)
moves=0
while sum(piles)>0:
    for i in range(len(piles)-1,0,-1):
        if piles[i-1]<piles[i]:
            piles[i]=piles[i]-piles[i-1]
            if piles[i] in p:
                piles.remove(piles[i])
                moves+=1

Answer 1

您可以使用带有“可接受的”启发式函数的 A* 算法。

当我们有一个不同值的列表时，我们最多只能希望取一堆，这样从中减去该金额的其他堆现在都与未进行减法的另一堆匹配。这意味着我们最多可以减少所选桩和其他桩的一半的桩数，因此变为 (-1)/2

所以我们至少需要 1+floor(log ₂ ) 步才能达到目标。我们可以在 [1,2,3,4,5,6,7] 中看到这个最小值的一个实例。此特定输入的最佳解决方案始终采用中间值，因此每次移动我们都会将列表减半：

• 取 4，结果 => [1,2,3,1,2,3] => [1,2,3]
• 取 2，结果 => [1, 1] => [1]
• 取1，完成。

下面是采用该启发式的 A* 算法的实现，并将配置标记为“已访问”，以避免两次求解相同的桩配置：

from heapq import heappush, heappop

def food(piles):
    if not piles:
        return 0
    node = frozenset(piles)
    heap = [(len(node).bit_length(), 0, node, [])]
    visited = set()

    while heap:
        heuristic, cost, node, moves = heappop(heap)
        if len(node) == 1:
            return moves + [min(node)]
        if len(node) == 2:
            return moves + [min(node), max(node) - min(node)]
        cost += 1
        for amount in node:
            neighbor = frozenset(pile - amount if pile > amount else pile
                                 for pile in node if pile != amount)
            if neighbor not in visited:
                visited.add(neighbor)
                heappush(heap, (cost + len(neighbor).bit_length(), cost, neighbor, 
                                moves + [amount]))

此代码返回要执行的移动列表。如果只需要返回最少的步数，那么上面可以简化为：

def food(piles):
    if not piles:
        return 0
    node = frozenset(piles)
    heap = [(len(node).bit_length(), 0, node)]
    visited = set()

    while heap:
        heuristic, cost, node = heappop(heap)
        if len(node) <= 2:
            return heuristic
        cost += 1
        for amount in node:
            neighbor = frozenset(pile - amount if pile > amount else pile
                                 for pile in node if pile != amount)
            if neighbor not in visited:
                visited.add(neighbor)
                heappush(heap, (cost + len(neighbor).bit_length(), cost, neighbor))