algorithm - 有人可以解释解决此 Google Code Jam 问题的算法之一吗？

Question

我指的是 Shopping Plan problem来自练习题。这是一个链接 the solutions page .

Answer 1

不看解决方案，这似乎是一个标准 DP .

每个州都由剩余商品列表(2^15 组合)和汽车的当前位置(50 商店 + 1 原始位置 = 51 可能的选项)。

从一种状态过渡到另一种状态很容易。

def minCost(itemsLeft, currentPosition)
    current_minimum = INFINITY

    for (each store in the list) {
        if (store.containsSomeOf(itemsLeft)) {
            candidate = minCost(itemsLeft - store.items, store)  
                     + cost_of_items_bought_at_store + cost_of_driving
            current_minimum = min(current_minimum, candidate)
        }
    }

    return current_minimum
end

自然地，itemList 表示为位掩码而不是实际列表。

您还需要考虑易腐烂的元素，但这纯粹是技术问题。

最后，您需要申请 memoization递归或将其重写为纯 DP。