背包的变化 - 确切重量的最低总成本

Question

有一些项目类型（N种），每种都有重量wi和成本ci。每一个都有无限的数目。问题是制作一个背包，精确的重量（W）和最小的物品总成本。我知道我应该在这种情况下使用动态，但它不是一个普通的背包问题，我找不到关系。我也发现了一些类似的问题，但我没有理解这些解决方案。这里是链接1,2。 如何使用DP来解决它？

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 

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大的重量。

然后，您可以使用递归算法使用memoization实施此方法，并根据您认为合适的实际解决方案进行存储（k s在递归中）。

编辑如果我们注意到有两种情况会影响min_cost(i, W)，那么可以通过建议加快速度。这种情况是第一次的时候并不需要在所有即min_cost(i+1, W)以及何时使用第i个项目，我们要至少一次使用第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)