I have coins for 10, 30 and 50. But I want to use only M coins to get a given sum.
I have this code (from this as reference) that just find all possible ways to get the total sum without applying the condition of using only M coins.
static long countWays(int coins[], int n, int sum)
{
// Time complexity of this function: O(n*sum)
// Space Complexity of this function: O(sum)
// table[i] will be storing the number of solutions
// for value i. We need sum 1 rows as the table is
// constructed in bottom up manner using the base
// case (sum = 0)
long[] table = new long[sum 1];
// Initialize all table values as 0
Arrays.fill(table, 0);
// Base case (If given value is 0)
table[0] = 1;
// Pick all coins one by one and update the table[]
// values after the index greater than or equal to
// the value of the picked coin
for (int i = 0; i < n; i )
for (int j = coins[i]; j <= sum; j )
table[j] = table[j - coins[i]];
return table[sum];
}
// Driver Function to test above function
public static void main(String args[])
{
int coins[] = { 10, 30, 50 };
int n = coins.length;
int sum = 80;
System.out.println(countWays(coins, n, sum));
}
How can we add that condition for this problem or is there any alternate approach for this.
For example:
M=4 and sum = 80
Output 2.
Explanation:
case 1 : 10*2 30*2 = 80 ( used 4 coins i.e. M coins)
case 2 : 10*3 50*1 = 80 ( used 4 coins i.e. M coins)
CodePudding user response：
One way to think about this problem is to count in a different base system. You use the number of unique coins as the base. So for your example of 10, 30, and 50, the base would be 3.
Now you need numbers in that base system that have the correct number of digits, which is 4 for your example. Since each digit can be only one of 3 values in base 3 (0, 1, or 2), the total number of possibilites is 3 raised to the power of 4, or 81.
Thus we can count from 0 to 80 in decimal, and convert that decimal number to a four digit base 3 number using stacked repeated division.
Here's what those four digit base 3 numbers would look like:
0 in base 3: [0, 0, 0, 0]
1 in base 3: [0, 0, 0, 1]
2 in base 3: [0, 0, 0, 2]
3 in base 3: [0, 0, 1, 0]
4 in base 3: [0, 0, 1, 1]
5 in base 3: [0, 0, 1, 2]
6 in base 3: [0, 0, 2, 0]
7 in base 3: [0, 0, 2, 1]
8 in base 3: [0, 0, 2, 2]
9 in base 3: [0, 1, 0, 0]
10 in base 3: [0, 1, 0, 1]
11 in base 3: [0, 1, 0, 2]
12 in base 3: [0, 1, 1, 0]
13 in base 3: [0, 1, 1, 1]
14 in base 3: [0, 1, 1, 2]
15 in base 3: [0, 1, 2, 0]
16 in base 3: [0, 1, 2, 1]
17 in base 3: [0, 1, 2, 2]
18 in base 3: [0, 2, 0, 0]
19 in base 3: [0, 2, 0, 1]
20 in base 3: [0, 2, 0, 2]
21 in base 3: [0, 2, 1, 0]
22 in base 3: [0, 2, 1, 1]
23 in base 3: [0, 2, 1, 2]
24 in base 3: [0, 2, 2, 0]
25 in base 3: [0, 2, 2, 1]
26 in base 3: [0, 2, 2, 2]
27 in base 3: [1, 0, 0, 0]
28 in base 3: [1, 0, 0, 1]
29 in base 3: [1, 0, 0, 2]
30 in base 3: [1, 0, 1, 0]
31 in base 3: [1, 0, 1, 1]
32 in base 3: [1, 0, 1, 2]
33 in base 3: [1, 0, 2, 0]
34 in base 3: [1, 0, 2, 1]
35 in base 3: [1, 0, 2, 2]
36 in base 3: [1, 1, 0, 0]
37 in base 3: [1, 1, 0, 1]
38 in base 3: [1, 1, 0, 2]
39 in base 3: [1, 1, 1, 0]
40 in base 3: [1, 1, 1, 1]
41 in base 3: [1, 1, 1, 2]
42 in base 3: [1, 1, 2, 0]
43 in base 3: [1, 1, 2, 1]
44 in base 3: [1, 1, 2, 2]
45 in base 3: [1, 2, 0, 0]
46 in base 3: [1, 2, 0, 1]
47 in base 3: [1, 2, 0, 2]
48 in base 3: [1, 2, 1, 0]
49 in base 3: [1, 2, 1, 1]
50 in base 3: [1, 2, 1, 2]
51 in base 3: [1, 2, 2, 0]
52 in base 3: [1, 2, 2, 1]
53 in base 3: [1, 2, 2, 2]
54 in base 3: [2, 0, 0, 0]
55 in base 3: [2, 0, 0, 1]
56 in base 3: [2, 0, 0, 2]
57 in base 3: [2, 0, 1, 0]
58 in base 3: [2, 0, 1, 1]
59 in base 3: [2, 0, 1, 2]
60 in base 3: [2, 0, 2, 0]
61 in base 3: [2, 0, 2, 1]
62 in base 3: [2, 0, 2, 2]
63 in base 3: [2, 1, 0, 0]
64 in base 3: [2, 1, 0, 1]
65 in base 3: [2, 1, 0, 2]
66 in base 3: [2, 1, 1, 0]
67 in base 3: [2, 1, 1, 1]
68 in base 3: [2, 1, 1, 2]
69 in base 3: [2, 1, 2, 0]
70 in base 3: [2, 1, 2, 1]
71 in base 3: [2, 1, 2, 2]
72 in base 3: [2, 2, 0, 0]
73 in base 3: [2, 2, 0, 1]
74 in base 3: [2, 2, 0, 2]
75 in base 3: [2, 2, 1, 0]
76 in base 3: [2, 2, 1, 1]
77 in base 3: [2, 2, 1, 2]
78 in base 3: [2, 2, 2, 0]
79 in base 3: [2, 2, 2, 1]
80 in base 3: [2, 2, 2, 2]
The integer in each resulting array (the base 3 number) represents which coin from the original coin values should go in that spot (0 = 10, 1 = 30, 2 = 50).
For example, the number 61 in decimal is 2021 in base 3:
61 in base 3: [2, 0, 2, 1]
The resulting coin combination for that number would be:
50, 10, 50, 30
Here's the code that generated the list of base 3 numbers above:
import java.util.Arrays;
class Main {
public static void main(String[] args) {
int sum = 80;
int numCoins = 4;
int[] coins = new int[]{10, 30, 50};
int base = coins.length;
int combos = (int)Math.pow(base, numCoins);
int[][] combinations = new int[combos][];
for(int d=0; d<combos; d ) {
combinations[d] = convertToBase(d, base, numCoins);
System.out.println(d " in base " base ": " Arrays.toString(combinations[d]));
}
}
public static int[] convertToBase(int decimalNumber, int base, int numDigits) {
int[] digits = new int[numDigits];
int index = digits.length - 1;
int quotient = decimalNumber;
while (quotient > 0) {
digits[index] = quotient % base;
index--;
quotient = quotient / base;
}
return digits;
}
}
Now that you have all possible combinations of four coins, you need to add up the values from each combo and see if they add up to 80.
Here's a new main() to do just that:
public static void main(String[] args) {
int sum = 80;
int numCoins = 4;
int[] coins = new int[]{10, 30, 50};
int base = coins.length;
int combos = (int)Math.pow(base, numCoins);
int[][] combinations = new int[combos][];
for(int d=0; d<combos; d ) {
combinations[d] = convertToBase(d, base, numCoins);
String combo = "";
int curSum = 0;
for(int coinChoice : combinations[d]) {
combo = combo coins[coinChoice] " ";
curSum = curSum coins[coinChoice];
}
if (curSum == sum) {
System.out.println("Coins: " combo " = " curSum);
}
}
}
Producing the following output:
Coins: 10 10 10 50 = 80
Coins: 10 10 30 30 = 80
Coins: 10 10 50 10 = 80
Coins: 10 30 10 30 = 80
Coins: 10 30 30 10 = 80
Coins: 10 50 10 10 = 80
Coins: 30 10 10 30 = 80
Coins: 30 10 30 10 = 80
Coins: 30 30 10 10 = 80
Coins: 50 10 10 10 = 80
Notice that there are repeats because the same combination of coin denominations could be put into different positions of the four slots.
If you want to get rid of duplicates, you could SORT the resulting combos and add them to a Hashmap if they don't already exist (add import java.util.HashMap;):
public static void main(String[] args) {
int sum = 80;
int numCoins = 4;
int[] coins = new int[]{10, 30, 50};
int base = coins.length;
int combos = (int)Math.pow(base, numCoins);
int[][] combinations = new int[combos][];
HashMap<String, String> uniqueCombos = new HashMap<String, String>();
for(int d=0; d<combos; d ) {
combinations[d] = convertToBase(d, base, numCoins);
String combo = "";
int curSum = 0;
for(int coinChoice : combinations[d]) {
combo = combo coins[coinChoice] " ";
curSum = curSum coins[coinChoice];
}
if (curSum == sum) {
Arrays.sort(combinations[d]);
String key = Arrays.toString(combinations[d]);
if (!uniqueCombos.containsKey(key)) {
uniqueCombos.put(key, combo);
System.out.println("Coins: " combo " = " curSum);
}
}
}
}
Now we only get the two unique combinations in our output:
Coins: 10 10 10 50 = 80
Coins: 10 10 30 30 = 80
Here is the final version of the entire program:
import java.util.Arrays;
import java.util.HashMap;
class Main {
public static void main(String[] args) {
int sum = 80;
int numCoins = 4;
int[] coins = new int[]{10, 30, 50};
int base = coins.length;
int combos = (int)Math.pow(base, numCoins);
int[][] combinations = new int[combos][];
HashMap<String, String> uniqueCombos = new HashMap<String, String>();
for(int d=0; d<combos; d ) {
combinations[d] = convertToBase(d, base, numCoins);
String combo = "";
int curSum = 0;
for(int coinChoice : combinations[d]) {
combo = combo coins[coinChoice] " ";
curSum = curSum coins[coinChoice];
}
if (curSum == sum) {
Arrays.sort(combinations[d]);
String key = Arrays.toString(combinations[d]);
if (!uniqueCombos.containsKey(key)) {
uniqueCombos.put(key, combo);
System.out.println("Coins: " combo " = " curSum);
}
}
}
}
public static int[] convertToBase(int decimalNumber, int base, int numDigits) {
int[] digits = new int[numDigits];
int index = digits.length - 1;
int quotient = decimalNumber;
while (quotient > 0) {
digits[index] = quotient % base;
index--;
quotient = quotient / base;
}
return digits;
}
}
CodePudding user response：
// Pick all coins one by one and update the table[] // values after the index greater than or equal to // the value of the picked coin for (int i = 0; i < n; i ) for (int j = coins[i]; j <= sum; j ) table[j] = table[j - coins[i]];
The overall direction is correct, Dynamic Programming is the right tool for this problem.
But there's a couple of serious mistakes in your solution:
The outer
for-loop should iterate over the coins, but in the snippet above, the outer loop iterates over the amounts (indexirepresents a particular amount). As a consequence, as the end result you'll get not a number of distinct Combinations, but a number of Permutations because in the approach you've taken two identical sets of coins arranged differently would be taken into account. For example, based on the logic of the code permutations like10 10 50 10and10 10 10 50would contribute the amount of80, which not correct according to the problem description.The second issue is much easier to spot, but nevertheless it's important: you're not checking if the array index to which you're referring to exists, which would lead to an
ArrayIndexOutOfBoundsException.
So, the main takeaway - we number the number of Combinations, and for that we need to consider each coin separately from other coins, i.e. the outer loop should perform iteration over the given array of coins.
To make the solution more comprehensible, I'll represent each combination of coins and each group of coin-combinations having the same total amount as objects Combination and Combinations respectively.
The array that would accumulate the result would be of type Combinations[]. Each Combination has two properties: limit and coinCount representing the required and current number of coins respectively. Combinations which coinCount exceeds the limit would be discarded on the fly, the rest would filtered out while producing the resulting value.
public static long countWays(int[] coins, int n, int sum) {
Combinations[] table = new Combinations[sum 1];
table[0] = Combinations.withOneNoCoinsComb(n);
for (int coin : coins) {
for (int i = 0; i < table.length; i ) {
// no combinations representing this amount or i coin exceeds the sum
if (table[i] == null || i coin > sum) continue;
if (table[i coin] == null) {
table[i coin] = Combinations.getEmpty(); // creating an empty Combinations instance
}
table[i coin].addCombinations(table[i]); // adding the combinations from the previous array position representing amount i
}
}
return table[sum].getValidCombCount();
}
Custom classes Combinations and Combination:
public class Combinations {
private List<Combination> comb = new ArrayList<>();
private Combinations() {}
public void addCombinations(Combinations other) {
for (Combination c : other.comb) {
if (c.canAdd()) this.comb.add(Combination.copyOf(c).addCoin());
}
}
public int getValidCombCount() {
return (int) comb.stream().filter(Combination::isValid).count();
}
private static Combinations withOneNoCoinsComb(int limit) {
Combinations oneComb = new Combinations();
oneComb.addCombination(new Combination(limit));
return oneComb;
}
private static Combinations getEmpty() {
return new Combinations();
}
public void addCombination(Combination c) {
comb.add(c);
}
// getters
}
public class Combination {
private final int limit; // m - max number of coins
private int coinCount;
public Combination(int limit) {
this.limit = limit;
}
public Combination(int limit, int coinCount) {
this.limit = limit;
this.coinCount = coinCount;
}
public Combination addCoin() {
coinCount ;
return this;
}
public boolean canAdd() {
return coinCount <= limit;
}
public boolean isValid() {
return coinCount == limit;
}
public static Combination copyOf(Combination c) {
return new Combination(c.getLimit(), c.getCoinCount());
}
// getters
}
main()
public static void main(String[] args) {
System.out.println(countWays(new int[]{10, 30, 50}, 4, 80));
}
Output:
2