3

0/1 背包的概念 - 使用给定的重量填充 W 重量的背包。目标是最大化利润。Ans-Problem 可以通过采用特定权重或不采用特定权重来解决，具体取决于哪个获得最大利润。通过这种方式可以计算出最优解。

现在，最小硬币找零问题 - 找到最小号码。硬币做出特定的改变。Ans-根据我的想法，可以通过取或不取特定硬币来解决，这取决于哪一个给出的最小值。硬币。只有 0/1 背包中的最大值条件会被反转。

但在实际的解决方案中是这样 的——在 geeksforgeeks 上给出的答案

现在，最小硬币变化问题的变化 - 我们必须为特定变化找到所有可能的硬币组合，遵循背包的概念。我不明白为什么？

就像这里完成了-

请帮助我理解为什么我的背包思维过程不适用于最低限度。硬币做出特定的改变。我哪里错了？还是我对 0/1 背包的概念有误，如果是，请解释两者。

4

1 回答 1

2

这段代码给出了在动态规划中使用 0/1 背包概念的最小硬币找零解决方案。在这里，我将要填充的二维矩阵的第 0 行初始化为 Integer.MAX_VALUE-1 并更新每个面额条目的值，以相应地在问题中求和。矩阵的最后一个元素给出了解决方案，即达到总和的最小硬币数量。如果没有通过给定的面额获得适当的总和，我返回-1。

public static int coinsChange(int denomination[],int sum){
    Arrays.sort(denomination);
    int[][] coins = new int[denomination.length+1][sum+1];
    for(int sumIdx = 0; sumIdx<= sum;sumIdx++){
          coins[0][sumIdx] = Integer.MAX_VALUE-1;
    }
    for(int i =1;i<=denomination.length;i++){
        for(int j = 1;j<=sum;j++){
            if(j>=denomination[i-1]){
                coins[i][j]=Integer.min(coins[i-1][j],coins[i][j-denomination[i-1]]+1);
             }
            else{
                coins[i][j] = coins[i-1][j];
             }

        }
   }
   if (coins[denomination.length][sum] == Integer.MAX_VALUE-1){
        System.out.println("No solution found");
        return -1;
    }

   return coins[denomination.length][sum];
}
于 2015-11-22T05:54:59.733 回答