Алгоритм динамического изменения монет (оптимальные результаты)

Мне дана эта часть кода в динамическом программировании (которая находит наилучшую комбинацию изменения монеты. Например, если у нас есть две монеты значения 3 и 4 -> {3, 4}, и сумма, которую мы хотим внести, например, sum = 11, ответ заключается в том, что нам нужно всего 3 монеты (2 монеты со значением = 4 и 1 монеты со значением = 3). хорошо, но не так, как я хочу

Я пытаюсь обратный инжиниринг ниже код так, что обеспечит более четкий ответ, как это:.Алгоритм динамического изменения монет (оптимальные результаты)

Total coins:3 , #of Coins with value "3" = 1, #of Coins with value "4" = 2

количество полных монет для данной суммы может из этого массива минимум [сумма]. Но остальная информация, которую я пытаюсь получить (какая монета - какое значение), кажется почти невозможной. Также из массива монет [sum] [0] я могу найти только последнюю использованную монету, в этом примере ее 3.

Inputs: sum=11 ,int[] valueCoins = new int[]{3,4}; 
Output: 
1 10011 0(0) 
2 10011 0(0) 
3 1 3(0) 
4 1 4(0) 
5 10011 0(0) 
6 2 3(3) 
7 2 3(4) 
8 2 4(4) 
9 3 3(6) 
10 3 3(7) 
11 3 3(8)

Как вы можете видеть, он проверяет все, от 1 до 11, но затем она достигает 11 он сохраняет правильное количество монет (3) и последнюю монету, (3).

public class MinimumCoin { 

    public static void main(String args[]){ 

     int[] valueCoins = new int[]{3,4}; 
     int sum = 11; 
     int[] minimum = new int[sum+1]; 
     int[][] coins = new int[sum+1][2]; 

     /* initializing the minimum of every sum to infinity */ 
     for(int i = 1; i < minimum.length; i++){ 
      minimum[i] = sum + 10000; 
     } 
     /* initializing that for minumum sum of zero, 0 coin is required */ 
     minimum[0] = 0; 

     for(int i = 1; i <= sum; i++){ 
      for(int j = 0; j <valueCoins.length; j++){ 
       if(valueCoins[j] == i){ 
        minimum[i] = 1; 
        coins[i][0] = i; 
        coins[i][1] = 0; 
       } 
       else if((valueCoins[j] < i) && (((minimum[i-valueCoins[j]]) + 1) < minimum[i])){ 

        minimum[i] = (minimum[i-valueCoins[j]]) + 1; 
        coins[i][0] = valueCoins[j]; 
        coins[i][1] = (i-valueCoins[j]); 
       } 
      } 
     } 

     for(int k = 1; k < minimum.length; k++){ 
      System.out.println(k + " " + minimum[k] + " " + coins[k][0] +"("+ coins[k][1] +")"); 
     } 
    } 
}

Спасибо за любой ввод!

~ Привет, S

источник

2013-02-23 Steve Brn

В чем вопрос? –

Проблема заключается в том, что значения в coins являются значением монет, а не на счете. coins:

0 0 0 3 0 0 3 3 4 3 3 3 
0 0 0 0 4 0 3 4 4 6 7 8

Так что вам нужно восстановить счетчики:

for(int k = 1; k < minimum.length; k++) 
{ 
    int count1 = 0, count2 = 0, pos = k; 
    if (coins[pos][1] > 0) 
     while (true) 
     { 
     if (coins[pos][0] == 3) count1++; 
     if (coins[pos][0] == 4) count2++; 
     if (coins[pos][1] == 3) count1++; 
     if (coins[pos][1] == 4) count2++; 
     if (coins[pos][1] < 5) // stop when 0/3/4 
      break; 
     pos = coins[pos][1]; 
     } 
    System.out.println(k + " " + minimum[k] + " " + 
         count1 + " of coin 3, " + count2 + " of coin 4"); 
}

Они также варианты, чтобы решить эту проблему:

Have строки для каждого числа появлений монеты , Если у вас есть 2 монеты, и каждый может появиться 5 раз, у вас будет 5x2 = 10 строк.
Есть строки следующим образом:
- строка 1 = 1 монеты 1
- строка 2 = 1 монеты 2
- строка 3 = 2 монеты 1
- строка 4 = 2 монеты 2
- строка 5 = 4 монеты 1
- строка 6 = 4 монеты 2
- строка 7 = 8 монет 1
- строка 8 = 8 монет 2
- ...

Последний является красивым более сложным, но предпочтительным, так как там будет много меньше строк для намного большего количества монет.

источник

2013-02-23 11:13:08 Dukeling

Алгоритм динамического изменения монет (оптимальные результаты)

ответ

Смежные вопросы