java - 计算从 167.37 美元中赚取(钱)零钱的不同方式？

Question

这是一道面试题:

Given an amount, say $167.37 find all the possible ways of generating the change for this amount using the denominations available in the currency?

谁能想到空间和时间高效的算法和支持代码，请分享。

这是我编写的(有效的)代码。我正在尝试找到它的运行时间，感谢任何帮助

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

}

Answer 1

编辑

这是组合/子集问题的具体示例，已在此处回答。

Finding all possible combinations of numbers to reach a given sum

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

原始答案

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

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

但是，动态规划方法并不能保证很快。

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