otak info official Logo   
OTAK.INFO
Personal Blog

Hariyanto Lim

정길상 / 鄭吉祥
Home   Last Posts  
 
Please login to see more topics and discussion categories.
 
goto main category list >> Life experiences >> Something I did

Title : Solving coin problem with limited coin values
Total Reply : 1
Total View : 3358


Harry
Harry
Total thread: 131
Total reply: 50

Post #136
Solving coin problem with limited coin values
Finding total combination of limited coins change to specific value, this is not a common question in our daily life, but sometime we need to solve this question. I was given this problem during my job seeking test, the solution to this problem is very simple but I was so frustrated to create this algorithm.

Case scenario :

Need to find combination of total value 20
Coin values : 1, 5, 10
Limited coin total : 5, 3, 2
Total coins are 10 (5 + 3 + 2)

So there are 5 coins of 1, 3 coins of 5 and 2 coins of 10.

How to solve it :

  1. Using Java Comparator to sort the coin values, lowest value is the first
    I.E.: 1 → 5 → 10
    int coinValues[] = {1, 5, 10}
    int coinTotals[] = {5, 3, 2}
  2. Calculate total MAXIMUM combination (= X) with formula :
    (coin A total + 1) * (coin B total + 1) * … (coin N total + 1)
    for our example : (5 + 1) * (3 + 1) * (2 + 1) = 72 ==> X
  3. Calculate "divider" of each coin type with formula :
    total of PREVIOUS coins (NOTE: the first coin divider is always 1)
    int coinDividers[] = { 1, 6, 24}
    '
    '.str_replace('
    ', ' ', '
    int iTotalPreviousDivider = 1; // start value
    for(int i = 0; i < iCoinTypeTotal; i++) {
    coinValue[i] = sortedValidCoinOnly.get(i).value;
    coinTotal[i] = sortedValidCoinOnly.get(i).total;
    coinDivider[i] = iTotalPreviousDivider;

    // update total previous divider FOR NEXT COIN
    iTotalPreviousDivider *= (sortedValidCoinOnly.get(i).total + 1);
    }
    ').'
    '
  4. Calculate each “use coin total” for each X (combination) with formula :

    loop through all combinations (= I) from 0 to (X-1) → 0 to 71

    use coin total = ((int) (X / coinDividers[i])) % (coinTotals[i] + 1);
Falling in love with the world

Write : 2013-08-05 16:46:21
Last edit : 2013-08-05 18:23:25

Harry
Harry
Total thread: 131
Total reply: 50

Post #137
Simple solution of finding total combination to limited coin change problem
Reply #1
Based on the algorithm below, we loop through all combinations and we can easily find the correct/valid combination.

'
'.str_replace('
', ' ', '
private ArrayList<HashMap<Integer, Integer>> searchValidCoinCombination(final int iT, final int []coinValues, final int []coinTotals, final int []coinDividers) {
ArrayList<HashMap<Integer, Integer>> result = new ArrayList<HashMap<Integer, Integer>>();

int iTotalCoinType = coinValues.length;

// calculate total possible method
int iTotalMaxPossibleMethod = 1;
for(int i = 0; i < iTotalCoinType; i++) {
iTotalMaxPossibleMethod *= (coinTotals[i] + 1);
}

// 20130721 : limit max possible method
if(iTotalMaxPossibleMethod > MAXLOOP) {
iTotalMaxPossibleMethod = MAXLOOP;
}

// loop thru all possible method .. THIS IS MAIN LOGIC ============
HashMap<Integer, Integer> combination = new HashMap<Integer, Integer>(); // create it
for(int method = 0; method < iTotalMaxPossibleMethod; method++) {

int iCombinationTotal = 0; // reset

int usedCoinTotal[] = new int[iTotalCoinType];

for(int i = 0; i < iTotalCoinType; i++) {

// =INT(MOD((method/divider), (coinTotal + 1))
//int iUsedCoinTotal = (int) (Math.floor(method / coinDividers[i]) % (coinTotals[i] + 1));
int iUsedCoinTotal = ((int) (method / coinDividers[i])) % (coinTotals[i] + 1);
usedCoinTotal[i] = iUsedCoinTotal;
iCombinationTotal += (coinValues[i] * iUsedCoinTotal);

// build "combination"
//combination.put(coinValues[i], iUsedCoinTotal);
}

Logger("method " + method + ", coin values : " + usedCoinTotal[0] + ", " + usedCoinTotal[1] + ", " + usedCoinTotal[2]);

// compare total
if(iCombinationTotal == iT) {
// ALWAYS create new HASHMAP() generate a lot of memory allocation and SLOW
// so we use .clear() method instead of always create new
//combination.clear(); // reset combination

// create NEW combination for NEXT possibility
combination = new HashMap<Integer, Integer>(); // create it

// build the combination AND put it to the result list
for(int i = 0; i < iTotalCoinType; i++) {

// =INT(MOD((method/divider), (coinTotal + 1))
int iUsedCoinTotal = (int) (Math.floor(method / coinDividers[i]) % (coinTotals[i] + 1));
//iCombinationTotal += (coinValues[i] * iUsedCoinTotal);

// build "combination"
combination.put(coinValues[i], iUsedCoinTotal);
}

// found it, so add it to the list
result.add(combination);

Logger("GOOD method " + method + ", combination total : " + iCombinationTotal + " == " + printCoinCombination(combination));
} else {
// this is NOT a valid combination
Logger("BAD method " + method + ", combination total : " + iCombinationTotal);// + " == " + printCoinCombination(combination));
}
}

return result;
}
').'
'

In this case, the total correct/valid combination to find total value of 20 using available 5 coins of 1, 3 coins of 3 and 2 coins of 10, the answer is 4

NOTE:
1. There is no need to create a recursive call function, the memory requirement is very small and the calculation is quite fast.
2. Each combination is calculated EXACTLY once.

Simple solution of finding total combination to limited coin change problem
Falling in love with the world

Write : 2013-08-05 16:52:49
Last edit : 2013-08-05 17:06:48

If you want to create a new reply then please login first.



www.OTAK.INFO
Since 19 January 2007
Page hit : 858,682

Code update 24th June 2013
Brain is a very capable to solve big problems
but requires constant reminders about how to.
peace bird