变体背包问题 - 精确重量下的最小总成本

Question

有N种物品，每种物品都有自己的重量wi和价值ci。每种物品的数量是无限的。问题是将这些物品放入一个容量为W的背包中，使得背包中的物品总重量恰好为W，并且总价值最小。虽然我知道应该使用动态规划算法来解决这个问题，但这不是一个常规的背包问题，我找不到它们之间的关系。我也找到了一些类似的问题，但我还没理解这些解决方案。以下是这些问题的链接：1，2。请问如何使用动态规划算法来解决这个问题？

- John Smith

Answer 1

f[i]代表当重量为i时的最小成本。g[i]代表是否可能精确地组合出重量为i；

f[0]=0;g[0]=true;
for (int i=0;i<N;i++)
    for (int j=0;j<W;j++)
        if (g[j]) {
            g[j+w[i]]=true;
            if (f[j+w[i]]==0||f[j+w[i]]>f[j]+c[i])
                f[j+w[i]]=f[j]+c[i];
        }

if (g[W]) return f[W];
else return 0;//impossible

- songlj

---

这个算法真的考虑了无限性的特点吗？（即每种类型都有无限数量）。我不太明白它是如何做到的。 - estan

Answer 2

假设你想找到完成重量为W的最小成本，并且c_i>0和w_i>0，那么我们可以定义min_cost(i, W)为仅使用物品i到N中重量为W的最小成本。

• 基本情况发生在只有一个物品时，即当i=N时。在这种情况下，解决方案是：

  min_cost(N, 0) = 0因为如果我们不使用物品N，则已经具有重量为0

  min_cost(N, W) = c_i * W / w_i如果W是w_i的倍数，即W mod w_i = 0

  min_cost(N, W) = Infinity否则，因为我们不能仅使用最后一个物品实现恰好为W的重量。

• 递归关系现在可以陈述为：

  min_cost(i, W) = min(c_i * k + min_cost(i+1, W - k * w_i))对于k=0直到W - k*w_i < 0

递归关系说明我们将尽可能多地使用物品i，同时我们还没有使重量大于W。

然后，您可以使用递归算法实现此方法，使用记忆化并根据需要存储实际解决方案（递归中的k）。

编辑建议可以加速，如果我们注意到有两种情况会影响min_cost(i, W)。这些情况是首先我们根本不需要使用第i个物品，即min_cost(i+1, W)和当我们至少要使用第i个物品时，这与min_cost(i, W - w_i)相同，因为我们可能使用物品i多次。这改变了我们的递归如下：

min_cost(i, 0) = 0         // We already reached our goal
min_cost(i, W) = Infinity  // if (W < 0 or i > N) then we can't get to W

min_cost(i, W) = min(min_cost(i+1, W), min_cost(i, W - w_i) + c_i)

- Gustavo Torres

---

这里有一个加速方法：如果对于给定的i，您按递增顺序计算权重，那么为了计算min_cost(i, W)，您只需要尝试将0个i项添加到i + 1 .. N项的最优解中，或者将1个i项添加到i .. N项的最优解中（因为您已经计算过它，因为它具有较低的重量）：min_cost(i, W) = min(min_cost(i+1, W), min_cost(i, W-w_i) + c_i)。在所有重量都为1的最坏情况下，这会减少W的因素。 - j_random_hacker

我将那个加速作为答案的编辑添加了进去。加速效果很好，而且更简单，谢谢！ - Gustavo Torres

不客气！附言：如果你在评论中某处写上“@j_random_hacker”，它会通知该人。我之所以注意到你的评论，是因为出于虚荣心我又回来了 :-P - j_random_hacker

@GustavoTorres，你有没有时间看一下这个 - https://math.stackexchange.com/questions/2415617？谢谢。 - Royi