编写一个可以使用适当的数据结构“做出改变”的Java程序？

Question

我有一个作业，我不知道如何解决它被要求这样做。

我不是要你解决整个问题！所以不要一看到“作业”这个词就不投赞成票。

这是一门关于数据结构与算法的课程，它说用合适的数据结构来解决问题。首先，我将作业复制到这里：

编写一个可以“做出改变”的Java程序。您的程序应该将两个数字作为输入，一个是收取的货币金额，另一个是给定的货币金额。然后，它应该返回每种纸币和硬币的号码，作为所给金额和所收费用金额之间的差额的零钱返还。分配给纸币和硬币的价值可以以任何现任或前任政府的货币制度为基础。尝试设计您的程序，使它返回的纸币和硬币数量尽可能少。

如果我没有理解错的话，我们必须编写一个程序，可以用最少的纸币和硬币来计算要还的钱的数量。

我们到目前为止只学习了堆栈、队列和链表，但我不知道如何使用这些数据结构中的一种来解决这个赋值。

哪种数据结构适合解决这样的问题？为什么？

Answer 1

这里有一个寻找最佳解的算法。基本上，它遍历所有可能的面额，寻找最短的变化值列表。

// How many cents in a dollar.
private static final int DOLLARS = 100;
// In cents.
private static final int[] denominations = {
    // $100
    100 * DOLLARS,
    // $50
    50 * DOLLARS,
    // $20
    20 * DOLLARS,
    // $10
    10 * DOLLARS,
    // $5
    5 * DOLLARS,
    // $2
    2 * DOLLARS,
    // $1
    1 * DOLLARS,
    // 50c
    50,
    // 25c
    25,
    // 5c
    5,
    // 1c
    1
};

private List<Integer> makeChange(int value) {
    // Null means none found so far.
    List<Integer> change = null;
    System.out.println("Make change for " + value);
    // For all denomination.
    for (int i : denominations) {
        // that is less than the value
        if (i <= value) {
            // Build a new candidate.
            List<Integer> newChange = new LinkedList<>();
            // Remember it.
            newChange.add(i);
            // If we are at zero we're done.
            if (i < value) {
                // Make change from the remaining value.
                List<Integer> theRest = makeChange(value - i);
                if (theRest != null) {
                    // Gode more.
                    newChange.addAll(theRest);
                }
            }
            // Is it shorter?
            if (change == null || newChange.size() < change.size()) {
                // Better.
                change = newChange;
                System.out.println("Better change for " + value + " = " + change);
            }
        }
    }
    return change;
}

使用26这样的低数字进行尝试将在合理的时间长度内获得良好的结果。在10+美元关口附近，它将会很挣扎，因为它必须列举每一个排列的所有可能的子排列--即使它以前见过它们。

如果允许我们使用映射,我们可以通过记住以前的最佳计算（称为Memoisation）来改善问题。这一个可以处理更大的数字，因为它从来不需要重新计算任何数字的最佳变化。

// All the best lists I've seen so far.
Map<Integer, List<Integer>> memory = new HashMap<>();

private List<Integer> makeChangeUsingMap(int value) {
    // If we've seen this one before, use it.
    if (memory.containsKey(value)) {
        return memory.get(value);
    }
    // Null means none found so far.
    List<Integer> change = null;
    System.out.println("Make change for " + value);
    // For all denomination.
    for (int i : denominations) {
        // that is less than the value
        if (i <= value) {
            // Build a new candidate.
            List<Integer> newChange = new LinkedList<>();
            // Remember it.
            newChange.add(i);
            // If we are at zero we're done.
            if (i < value) {
                // Make change from the remaining value.
                List<Integer> theRest = makeChangeUsingMap(value - i);
                if (theRest != null) {
                    // Gode more.
                    newChange.addAll(theRest);
                }
            }
            // Is it shorter?
            if (change == null || newChange.size() < change.size()) {
                // Better.
                change = newChange;
                System.out.println("Better change for " + value + " = " + change);
                // Remember it.
                memory.put(value, change);
            }
        }
    }
    return change;
}

Answer 2

我会用地图。例如，75名代表如下：

100 -> 0
 50 -> 1
 20 -> 1
 10 -> 0
 5  -> 1
 ...
0.01 ->0

意思是零百张钞票、五十张钞票中的一张等等。