3

Problem Statement:

I need to get the best combination of denomination for a given number. Example: I have three denominations {50,25,10} and given number is 30 then list should return <10,10,10>. for number 80 it should return <50,10,10,10> as remaining 30 is not completely divide by 25. For 35 it should return <25,10> for 75 <50,25> for 65 <50,10>

This is somewhat similar to coin problem but I am not able to get the values of denominations.

Refence StackOverFlow Coin change DP solution to keep track of coins Here is what I have tried so far :

public static int[] minChange(int[] denom, int changeAmount) {
    int n = denom.length;
    int[] count = new int[changeAmount + 1];
    int[] from = new int[changeAmount + 1];

    count[0] = 1;
    for (int i = 0; i < changeAmount; i++ )
      if (count[i] > 0)
        for (int j = 0; j < n; j++ ) {
          int p = i + denom[j];
          if (p <= changeAmount) {
            if (count[p] == 0 || count[p] > count[i] + 1) {
              count[p] = count[i] + 1;
              from[p] = j;
            }
          }
        }

    // No solutions:
    if (count[changeAmount] == 0)
      return null;

    // Build answer.
    int[] result = new int[count[changeAmount] - 1];
    int k = changeAmount;
    while (k > 0) {
      result[count[k] - 2] = denom[from[k]];
      k = k - denom[from[k]];
    }
    return result;
  }

This works well if value are completely divisible by one of denomination other wise i doesn't work at all.

Community
  • 1
  • 1
Rahul Swami
  • 31
  • 2
  • 2
    And what is the question? – Robin Topper Apr 19 '17 at 13:47
  • 2
    shouldn't 65 be <25,10,10,10,10>? – ControlAltDel Apr 19 '17 at 13:47
  • 1
    The general case of this problem is NP-Hard – ControlAltDel Apr 19 '17 at 13:49
  • 1
    @ControlAltDel My bad , 65 should be <25,10,10,10,10>. Thanks !! – Rahul Swami Apr 19 '17 at 13:50
  • @RobinTopper Question is, I need to calculate the best divisible denomination of a given number. Hope this helps !! – Rahul Swami Apr 19 '17 at 14:03
  • The code above seems to be ok. What do you mean by "doesn't work at all"? – DAle Apr 19 '17 at 14:11
  • @DAle If given number is not completely divisible by any denomination, it return null. So If given number is 42, this code will not calculate the best possible combinations. – Rahul Swami Apr 19 '17 at 16:46
  • Please include your actual question in the question text. As it stands, the "best combination of denomination for a given number" is still unclear. What's the best, is it the one which contains the least number of elements? The one which is lexicographically the greatest (has the largest possible first coin, then the largest possible second coin, etc.)? The one which uses the least number of _different_ coins? Each of these guesses has some merit. – Gassa Apr 20 '17 at 14:14
  • In any case, what may help is viewing this as a knapsack problem and solving it in pseudopolynomial time. – Gassa Apr 20 '17 at 14:20

1 Answers1

0

Once you have the solution in the 2D array for the dynamic programming solution, you can find out what denominations were optimal by backtracking through your array from the end (arr[n][n]).

J. Michael Wuerth
  • 272
  • 1
  • 6