原创转载请注明出处:http://agilestyle.iteye.com/blog/2361927
Question:
Given a change amount, print all possible combinations using different sets of coins
Solution:
核心思想:递归
1. Sort coins from large to small based on amount
2. Determine how many large coins used
3. Calculate how much the amount left using a given number of large coins
4. Recursion to the deducted value using sub-set of the coins
5. Print out of the remaining amount dividable by the smallest coin amount
package org.fool.java.test; public class PrintAllCoinChangeCombinationTest { public static void main(String[] args) { int[] coins = {25, 10, 5, 1}; int[] counts = new int[coins.length]; System.out.println("All possible coin combinations of 10 cents are: "); printCombination(coins, counts, 0, 10); System.out.println("All possible coin combinations of 25 cents are: "); printCombination(coins, counts, 0, 25); } // coins are the sorted coins in descending order, larger positioned more front // counts record the number of coins at certain location // start index is keep cracking of from which coin we start processing after choosing one larger coin amount // total amount keep track of remaining amount left processing private static void printCombination(int[] coins, int[] counts, int startIndex, int totalAmount) { if (startIndex >= coins.length) { // format the print out as "amount=?*25 + ?*10 + ..." for (int i = 0; i < coins.length; i++) { System.out.print("" + counts[i] + " * " + coins[i] + " + "); } System.out.println(); return; } // notice if startIndex is the last one, we need check if it can be dividable by the smallest coin // if so, this is a good combination, otherwise, this is not possible combination thus discarded if (startIndex == coins.length - 1) { if (totalAmount % coins[startIndex] == 0) { // good combination // set the counts of coins at start index counts[startIndex] = totalAmount / coins[startIndex]; // proceed to recursive call printCombination(coins, counts, startIndex + 1, 0); // notice startIndex + 1 and remaining amount = 0 } } else { // we still have option to choose 0-N larger coins for (int i = 0; i <= totalAmount / coins[startIndex]; i++) { // for every cycle in a loop, we choose an arbitrary number of larger coins and proceed next counts[startIndex] = i; // notice we need to update the remaining amount printCombination(coins, counts, startIndex + 1, totalAmount - coins[startIndex] * i); } } } }
Console Output
Reference
https://www.youtube.com/watch?v=3VBjhiKUtmE&list=PLlhDxqlV_-vkak9feCSrnjlrnzzzcopSG&index=38
相关推荐
### 标题:Combinations of Intelligent Methods and Application #### 栈意与重点 该书的标题表明其主要内容是探讨不同智能方法的结合以及这些结合在实际中的应用。智能方法可以包括人工智能的各种子领域和技术,...
sioned expression (which in turn is based on the notion of data provenance), namely an expression that captures, in a compact way, the analysis result with respect to all possible combinations of ...
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephon
大师Donald E. Knuth(汉名高德纳)的著作,计算机程序设计与艺术第四卷3册:生成所有组合和分划Generating All Combinations and Permutations(中英)
**标题**:“The fantastic combinations of John Conway's new solitaire game life.pdf” **描述**:马丁·加德纳撰写的关于生命游戏的文章,希望对大家有所帮助。 本文档主要介绍了数学家约翰·康威(John ...
c c语言_leetcode 0017_letter_combinations_of_a_phone_number.zip
java入门 java_leetcode题解之17_Letter_Combinations_of_a_Phone_Number
js js_leetcode题解之17-letter-combinations-of-a-phone-number.js
c语言入门 C语言_leetcode题解之17-letter-combinations-of-a-phone-number.c
matlab导入excel代码utl_all_possible_pairs_of_rows 所有可能的行对。 关键字:sas sql join合并大数据分析宏oracle teradata mysql sas社区stackoverflow statistics人工智慧AI Python R Java Javascript WPS ...
《计算机程序设计艺术》(The Art of Computer Programming)是由美国著名计算机科学家唐纳德·克努特(Donald E. Knuth)编写的经典著作,该系列书籍在计算机科学领域具有里程碑式的意义。此系列不仅涵盖了广泛的...
As we’ll see, the clustered key is duplicated in every nonclustered index row, so keeping your clustered key small will allow you to have more index fit per page in all your indexes. Note The ...
Letter Combinations of a Phone Number"这个项目,它涉及到如何通过JavaScript实现电话号码数字到字母的映射。 首先,让我们理解这个问题的基本概念。电话号码通常使用数字来表示,但为了方便记忆,这些数字往往...
MAKEBITS - 生成 N 位的位数组,其中包含 1 和 0 的所有组合。 示例:makebits(3)' 产生 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 但当然你可以把它翻转到横向。 我用它来测试通信渠道。
proper combinations of threshold level and enhanced vaccination rate based on threshold policy can lead disease prevalence to a previously chosen level if eradication of disease is impossible.
- **(c) All of \(\mathbb{R}^3\)**: For three linearly independent vectors, all possible combinations can fill up the entire space of \(\mathbb{R}^3\). **2. Diagonals of a Parallelogram** Given ...
def coin_combinations(n, coins, target): dp = [0] * (target + 1) dp[0] = 1 for i in range(1, n + 1): for j in range(coins[i - 1], target + 1): dp[j] += dp[j - coins[i - 1]] return dp[target] `...
Lua can handle subtraction, negative numbers, numbers with decimal points, multiplication (using *), division (using /), exponentiation (using ^), and combinations of these. Here are some examples > ...