OTAK.INFO Personal Blog Hariyanto Lim 정길상 / 鄭吉祥 Home   Last Posts

>> Life experiences >> Something I did

Title : Solving coin problem with limited coin values
 HarryTotal thread: 131Total reply: 50Post #136 Solving coin problem with limited coin valuesFinding 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 20Coin values : 1, 5, 10Limited coin total : 5, 3, 2Total 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 :Using Java Comparator to sort the coin values, lowest value is the firstI.E.: 1 â†’ 5 â†’ 10int coinValues[] = {1, 5, 10}int coinTotals[] = {5, 3, 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 ==> XCalculate "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 valuefor(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);}').'```'Calculate each â€œuse coin totalâ€ for each X (combination) with formula :loop through all combinations (= I) from 0 to (X-1) â†’ 0 to 71use coin total = ((int) (X / coinDividers[i])) % (coinTotals[i] + 1); Falling in love with the worldWrite : 2013-08-05 16:46:21Last edit : 2013-08-05 18:23:25
 HarryTotal thread: 131Total reply: 50Post #137 Simple solution of finding total combination to limited coin change problemReply #1Based on the algorithm below, we loop through all combinations and we can easily find the correct/valid combination.'```'.str_replace('', ' ', ' private ArrayList> searchValidCoinCombination(final int iT, final int []coinValues, final int []coinTotals, final int []coinDividers) { ArrayList> result = new ArrayList>(); 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 combination = new HashMap(); // 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(); // 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 4NOTE: 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.Falling in love with the worldWrite : 2013-08-05 16:52:49Last edit : 2013-08-05 17:06:48