Динамическое программирование: почему мы не можем решить минимальное число. монеты, необходимые для изменения с концепцией ранца 0/1?

Question

Понятие 0/1Knapsack- Заполните рюкзак весом W с использованием заданных весов. Это максимизирует прибыль. Ans-Problem можно решить, взяв определенный вес или не принимая определенный вес, в зависимости от того, какой из них дает максимальную прибыль. Таким образом можно вычислить оптимальное решение.

Теперь проблема с изменением монеты мин. Найти минимальное значение. монет для внесения определенного изменения. Ans-Согласно тому, что я думал, его можно решить, взяв конкретную монету или нет, в зависимости от того, какой из них дает минимальное значение. монет. Только условие максимума в рюкзаке 0/1 будет отменено.

Но на самом растворе идет как this- Answer given on geeksforgeeks

теперь, изменение минимального изменения монетных проблемы, где все возможные комбинации монет, которые мы должны найти для конкретного изменения, концепция рюкзака является followed.I я не понимаю почему?

like here it is done-

Пожалуйста, помогите мне понять, почему моя мысль процесс ранца не работает для минимального ни в. монет для внесения определенного изменения. Где я иду не так? Или я ошибаюсь в концепции ранга 0/1, Если да, объясните, пожалуйста, оба.

Answer 1

Этот код дает минимальное решение о замене монет с использованием концепции ранцевания 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]; 
}