3

物品有多种类型（N 种），每种都有重量 wi 和成本 ci。每一个都有无数个。问题是制作一个具有精确（W）重量和最低物品总成本的背包。我知道在这种情况下我应该使用动态，但这不是常见的背包问题，我找不到关系。我也发现了一些类似的问题，但我不明白这些解决方案。这是链接1、2。怎么用DP来解决呢？

4

2 回答 2

4

让 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
于 2013-03-18T12:37:52.917 回答
2

假设您想找到完成重量W和所需的最低成本c_i > 0，w_i > 0然后我们可以将其定义为仅使用重量为 的项目min_cost(i, W)可以实现的最低成本iNW

  • 基本情况发生在我们只有一个项目时，因此当i=N. 在这种情况下，解决方案是：

    min_cost(N, 0) = 0因为如果我们不使用 itemN那么我们的权重就等于 0

    min_cost(N, W) = c_i * W / w_iifW是w_iie的倍数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尽可能多次使用 item，而我们没有使权重大于W。

然后，您可以使用递归算法实现此方法，使用记忆和存储您认为适合实际解决方案（k递归中的 s）。

编辑根据建议，如果我们注意到有两种情况会影响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)
于 2013-03-18T12:44:57.760 回答