计算一下从 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<Float> denominations,HashMap<Float,Integer> useddenominations)
    {
        if(amount<0)
            return;
        if(amount==0)
        {
            Iterator<Float> 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<Float> denominations = new LinkedList<Float>();


        denominations.add(ddollar);
        denominations.add(dollar);
        denominations.add(nikle);

        HashMap<Float,Integer> useddenominations = new HashMap<Float,Integer>();
        generatechange(amount, denominations, useddenominations);
    }

}

EDIT

这是组合/子集问题的具体示例，在此得到解答。

找出所有可能的数字组合以达到给定的总和 https://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum

---我保留下面的答案（因为它对某人有用），但是，不可否认，这不是这个问题的直接答案---

原答案

最常见的解决方案是动态规划：

首先，您找到更改 1 的最简单方法，然后使用该解决方案更改 2、3、4、5、6 等...在每次迭代时，您“检查”是否可以“向后”并减少答案中的硬币数量。例如，最多“4”，您必须添加便士。但是，一旦达到“5”，您就可以取出所有便士，并且您的解决方案只需要一枚硬币：镍币。但到了 9 点，你又必须添加便士，等等等等。

然而，动态规划方法并不能保证很快。

或者，您可以使用贪婪方法，不断地选择尽可能大的硬币。这非常快，但并不总能为您提供最佳解决方案。但是，如果您的硬币是 1 5 10 和 25 ，那么贪心法就可以完美工作，并且比线性规划方法快得多。