java - 条件为恰好使用 m 个硬币的硬币找零问题

Question

我有 10、30 和 50 的硬币。但我只想使用 M 硬币来获得给定的 sum。

我有这段代码(来自 this 作为引用)它只是找到所有可能的方法来获得总和，而不适用仅使用 M 硬币的条件。

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));
    }

我们如何为这个问题添加该条件，或者是否有任何替代方法。

例如:

M=4 and sum = 80

输出 2.

解释:

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)

约束:

M reaches up to 5000
sum reaches up to 250000

Answer 1

思考这个问题的一种方法是count in a different base system .您使用独特硬币的数量作为基础。因此，对于 10、30 和 50 的示例，底数为 3。

现在您需要该基本系统中的数字具有正确的位数，在您的示例中为 4。由于每个数字只能是 3 个基数(0、1 或 2)中的一个，因此可能的总数是 3 的 4 次方，即 81。

因此我们可以用十进制数从 0 到 80，然后使用 stacked repeated division 将该十进制数转换为以 3 为基数的四位数。 .

这是以 3 为基数的四位数字的样子:

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]

每个结果数组中的整数(以 3 为基数)表示原始硬币值中的哪个硬币应该放在那个位置(0 = 10、1 = 30、2 = 50)。

例如，十进制数 61 在基数 3 中为 2021:

61 in base 3: [2, 0, 2, 1]

该数字的最终硬币组合为:

50, 10, 50, 30

下面是生成上述 3 进制数字列表的代码:

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;
  }
  
}

现在您已经有了四种硬币的所有可能组合，您需要将每个组合的值相加，看看它们加起来是否为 80。

这是一个新的 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);

      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);
      }
    }
  }

生成以下输出:

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

请注意这里有重复，因为可以将相同面额的硬币组合放入四个插槽的不同位置。

如果你想去掉重复项，你可以对结果组合进行排序并将它们添加到 Hashmap 中。如果它们尚不存在(添加 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);
        }  
      }
    }
  }

现在我们在输出中只得到两个独特的组合:

Coins: 10 10 10 50  = 80
Coins: 10 10 30 30  = 80

这是整个程序的最终版本:

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;
  }
  
}