动态规划 - 将给定重量装入袋子的最低成本

Question

我们得到了一系列正权重成本，其中

cost[i]

表示将

i + 1

千克橙子装入袋子中的成本（基于 0 的索引）。假设每

w

公斤橙子的供应量无限，我们需要找到恰好购买

i + 1

公斤橙子的最低成本。

我很难得出这个问题的约束，因为我无法确定我们应该解决哪些子问题才能找到最终更大问题的解决方案。

因此，在解决了关于 SO 的动态编程问题后，我尝试首先实现递归强力解决方案，以了解哪些是较小的子问题。

import math

def solve(n, cost, w, curr_cost, stack, dp):
    if w < 0:
        return
    if w == 0:
        print(stack, curr_cost)
        res = min(res, curr_cost)
        return
    for i in range(n):
        stack.append(i + 1)
        solve(n, cost, w - (i + 1), curr_cost + cost[i], stack, dp)
        stack.pop()


n = 5
cost = [20, 10, 4, 50, 100]
w = 5
res = math.inf
dp = [math.inf for _ in range(w + 1)]
solve(n, cost, w, 0, [], dp)
print(res)

现在，我无法记住这个解决方案。记忆之后，我想知道我们如何识别问题中的约束以及如何使用它们来设计自下而上的方法。例如，如果我们制作一个维度为

2D

的

n x w

网格（经过一些提示后），我们知道对于行

0

，即

n=0

，该行中的所有单元格都将是

cost[0] * w

，因为我们仅有

1

公斤的橙子包。对于第

1

列，该列中的所有单元格都将是

cost[0]

，因为我们正好需要

1

kg 橙子，而这只有包装大小为

1

kg 的橙子才可能实现。现在，我如何使用这些信息来计算其他单元格的值。

    1  2  3  4  5 <- w
0   20 40 60 80 100
1   20 -  -  -  -
2   20 -  -  -  -
3   20 -  -  -  -
4   20 -  -  -  -
^n

即编写强力递归解决方案，识别较小的子问题，然后构建自下而上的解决方案。

我已经浏览了互联网和SO上的各种文章，但仍然无法获得解决动态规划问题的直觉。

Answer 1

如果我理解正确的话，这个问题实际上很容易转换为最短路径问题。每个权重将是图中的一个节点，所需的权重是目标节点。然后我们可以在这些节点之间绘制链接，其成本是这些节点之间差异的成本。例如，如果成本为

[20, 10, 4, 50, 100]

，则节点

20

和节点

22

之间的成本将为

10

(

costs[1]

)。然后我们可以简单地找到节点

0

和节点

w

之间的最短路径。

Python 实现可能如下所示：

import heapq

def calc(target_weight: int, weight_costs: list[int]):
    costs = [None] * (target_weight + 1)
    heap = []
    costs[0] = 0
    heapq.heappush(heap, (0, 0))
    while len(heap):
        cost, current_weight = heapq.heappop(heap)
        print(costs)
        if current_weight == target_weight:
            return cost
        for dw, dcost in enumerate(weight_costs, 1):
            ncost = cost + dcost
            nweight = current_weight + dw
            if nweight > target_weight:
                break
            if costs[nweight] is not None and costs[nweight] < ncost:
                continue
            costs[nweight] = ncost
            heapq.heappush(heap, (ncost, nweight))
    return -1

if __name__ == "__main__":
    target_weight = 5
    weight_costs = [20, 10, 4, 50, 100]
    print(calc(target_weight, weight_costs))