The problem with changing coins with an infinite number of coins of each denomination

Question

I want to know the idea of ​​an algorithm for a coin change problem, where each value has an infinite number of coins. Means how to apply DP (for example, a standard problem with changing a coin) For example, for example, in the set 1,10,15, a change of 35 gives - 2 coins of 10 and one coin 15

Also give me an idea of ​​the coarse-force algorithm for this. I know to iterate over all sets. But how to change the amount of each coin during rough forcing

Answer 1

I would think about building a solution one step at a time, inductively:

: 1c, 5c, 10c, 25c ( )

• 1c = 1 X 1c. 4 1c , .
• 5 5 c. 4c, 1 9.
• 10 1 X 10c. , 1 19.
• 20c 2 x 10c, 20 10.

, .

EDIT:
, :

x (x - ) n (n - , , ). - . :

1 {1c} 1 1c
2 {1c, 10c} i.e 2 1c 10c
3 {1c, 10c, 15c} ..... , .

, . ( 1 ),
cell(1, 5) == > 5c, {1c}
cell(2, 9) == > 9c {1c, 10c}
cell(3, 27) == > 27c {1c, 10c, 15c}
- cell(x, n)

Solution:
. , {1c}. 1 , cell(1, n)= {nx1c} (n 1c).

. , , () cell(2, 28) .. 28c {1c, 10c}. , 10c , . 3 (3 = 28/10 + 1)

Choice 1:
{1x10c}, ( cell(1, 18)). {1x10c, 18x1c}= 19 coins

Choice 2:
{2x10c}, - ( cell(1, 8)). {2x10c, 8x1c}= 10 coins

Choice 3:
10c, - ( cell(1, 28)). {28x1c}= 28 coins

, 2 , . . .

, cell(x, n), n/p + 1, p= x. - .

, .

Answer 2

:

int i,j,k;
for(i=0;i<35;i++){
  for(j=0;j<4;j++){
    for(k=0;k<3;k++){
      if(1*i+10*j+15*k == 35){
        //is this what you need?
        //minimum=min(minimum,(i+j+k));
      }
    }
  }
}

Answer 3

.

" " - , , .

, , ,

int[] greedy(int value, int[] coins) {
   int[] ans = ...;
   int v = coins.length - 1;
   int left = value;
   while (left > 0 && v >= 0) {
       if (coins[v] <= left) {
           ans.push(coins[v]);
       } else { 
           v--;
       }
   }
   return left == 0 ? ans : //representation impossible, 
                            //so you better do something;
}

, , ,

int f(int value, int[] coins) {
   int[] memo = new int[value + 1];
   Arrays.fill(memo, 1234567);
   memo[0] = 0;
   for (int coin : coins)
       for (int i = 0; i + coin <= value; i++)
           memo[i + coin] = min(memo[i + coin], memo[i] + 1);
   return memo[value];
}

, , : if memo[value] = 3, ​​, memo[value - coin] == 2, (value - coin), 0.

Answer 4

. :

35 = 1*2^5 + 0*2^4 + 0*2^3 + 0*2^2 + 0*2^1 + 1*2^0

:

var cash = 35;
var coins = [15, 10, 5, 1];
var change = {};
for(var i=0; i<coins.length; i++){
  change[coins[i]]  = Math.floor(cash/coins[i]);
  cash %= coins[i];
}
//change now contains:
//15:2, 10:0, 5:1, 1:0

Answer 5

You can run it here http://www.exorithm.com/algorithm/view/coin_change

function coin_change ($amount, $coins)
{
  $change = array();
  rsort($coins);
  for($i=0; $i<count($coins); $i++) {
    $change[$coins[$i]] = floor($amount/$coins[$i]);
    $amount = $amount % $coins[$i];
  }
  return $change;
}