计算（金钱）从167.37美元变化的不同方式？
这是一个面试问题：
给定金额，比如167.37美元，找到使用货币中可用面额生成此金额变化的所有可能方法？
任何想到空间和时间有效的算法和支持代码的人，请分享。
这是我写的（工作）代码。 我试图找到这个的运行时间，任何帮助表示赞赏
import java.util.HashMap; import java.util.Iterator; import java.util.LinkedList; import java.util.Map; public class change_generation { /** * @param args */ public static void generatechange(float amount,LinkedList denominations,HashMap useddenominations) { if(amount<0) return; if(amount==0) { Iterator it = useddenominations.keySet().iterator(); while(it.hasNext()) { Float val = it.next(); System.out.println(val +" :: "+useddenominations.get(val)); } System.out.println("**************************************"); return; } for(Float denom : denominations) { if(amount-denom < 0) continue; if(useddenominations.get(denom)== null) useddenominations.put(denom, 0); useddenominations.put(denom, useddenominations.get(denom)+1); generatechange(amount-denom, denominations, useddenominations); useddenominations.put(denom, useddenominations.get(denom)-1); } } public static void main(String[] args) { // TODO Auto-generated method stub float amount = 2.0f; float nikle=0.5f; float dollar=1.0f; float ddollar=2.0f; LinkedList denominations = new LinkedList(); denominations.add(ddollar); denominations.add(dollar); denominations.add(nikle); HashMap useddenominations = new HashMap(); generatechange(amount, denominations, useddenominations); } } 编辑
这是组合/子集问题的具体示例，在此回答。
找到所有可能的数字组合以达到给定的总和
—我保留下面的答案（因为它对某人有用），但是，诚然，这不是这个问题的直接答案—
原始答案
最常见的解决方案是动态编程：
首先，您找到了更改1的最简单方法，然后使用该解决方案对2,3,4,5,6等进行更改….在每次迭代中，您“检查”是否可以“向后“并减少答案中的硬币数量。 例如，最多为“4”，您必须添加便士。 但是，一旦你达到“5”，你可以删除所有的便士，而你的解决方案只需要一枚硬币：镍。 但是，直到9，你再次必须添加便士等等。
但是，动态编程方法并不是快速的。
或者，您可以使用贪婪的方法，在那里您可以不断选择最大的硬币。 这非常快，但并不总能为您提供最佳解决方案。 但是，如果你的硬币是1 5 10和25，贪婪的工作完美，并且比线性编程方法快得多。
Memoization（有点）是你的朋友。 C中的一个简单实现：
unsigned int findRes(int n) { //Setup array, etc. //Only one way to make zero... no coins. results[0] = 1; for(i=0; i
那么，我们在这里真正做的是说：
1）我们制作0币的唯一可行方法是0（这是我们的基本情况）
2）如果我们试图计算值m，那么让我们检查每个硬币k。 只要k <= m，我们就可以在解决方案中使用该硬币k
3）好吧，如果我们可以在解决方案中使用k，那么我们不能只为（mk）采用解决方案并将其添加到我们当前的总数中吗？
我试着在现实生活中对此进行建模。
如果你在收银台并且你知道你必须找到167.37美元，你可能最初认为200美元是“最简单”的投标，只有两个钞票。 然后，如果我有它，我可以考虑170美元，即100美元，50美元和20美元（三个音符）。 看看我要去哪里？
更正式的是，尝试使用最少数量的纸币/硬币进行过度投标。 这比完整的可能性更容易列举。
不要使用浮动，即使最小的不准确也会破坏你的算法。
从最大到最低的硬币/钞票。 对于每个可能的量，递归调用该函数。 当没有剩余硬币时，将其余硬币支付给其中并打印解决方案。 这是它在伪C中的样子：
#define N 14 int coinValue[N]={20000,10000,5000,2000,1000,500,200,100,50,20,10,5,2,1}; int coinCount[N]; void f(int toSpend, int i) { if(coinValue[i]>1) { for(coinCount[i]=0;coinCount[i]*coinValue[i]<=toSpend;coinCount[i]++) { f(toSpend-coinCount[i]*coinValue[i],i+1); } } else { coinCount[i]=toSpend; print(coinCount); } }
import java.util.HashMap; import java.util.Iterator; import java.util.LinkedList; import java.util.Map; public class change_generation { static int jj=1; public static void generatechange(float amount,LinkedList denominations, HashMap useddenominations) { if(amount<0) return; if(amount==0) { Iterator it = useddenominations.keySet().iterator(); while(it.hasNext()) { Float val = it.next(); System.out.println(val +" :: "+useddenominations.get(val)); } System.out.println("**************************************"); return; } for(Float denom : denominations) { if(amount-denom < 0) continue; if(useddenominations.get(denom)== null) useddenominations.put(denom, 0); useddenominations.put(denom, useddenominations.get(denom)+1); generatechange(amount-denom, denominations, useddenominations); useddenominations.put(denom, useddenominations.get(denom)-1); } } public static void main(String[] args) { float amount = 2.0f; float nikle=0.25f; float dollar=1.0f; float ddollar=2.0f; LinkedList denominations = new LinkedList (); denominations.add(ddollar); denominations.add(dollar); denominations.add(nikle); HashMap useddenominations = new HashMap(); generatechange(amount, denominations, useddenominations); } }