algorithm - 背包 0/1 算法 - 无限资源

Question

我遇到了思维问题，我很沮丧。我有一个背包问题的工作算法，使用动态编程，我在其中指定

• 最大负荷
• 物品（重量）

该算法使用这些物品计算背包的最佳填充量。但是现在我需要完全填充它，使用最少的项目，但我每个项目的数量都是无限的。（这些项目有重量{1; w1; w2; ...}，所以总是可以完成）。

我如何在“经典”算法中适应这个？

谢谢

Answer 1

让

• M = 需要填写的金额
• w[] = 权重数组
• dp[] = 最佳填充数组（dp[i] 包含填充重量 i 所需的最少项目数）。

 initialize the dp array with INFINITY, dp[0] = 0;
 for(i = 0;i<size of w;i++) {
    for(j = 1;j<=M;j++) {
       if(j-w[i] >= 0) {
          dp[j] = min(dp[j], dp[j-w[i]]+1);
       }
    }
 }

 final solution is the value of dp[M];