是否有针对此货币兑换问题的最佳解决方案? [英] Is there a more optimal solution to this money change problem?

问题描述

我被要求创建一种方法，该方法将:

I was asked to create a method that would:

• 返回Change对象，如果没有可能的更改，则返回null
• 机器"有无限的账单:2、5和10
• 零钱对象必须返回尽可能少的账单

这是在codingame.com上提出的一个问题，希望对此进行进一步调查.这是代码:

This was a question asked in codingame.com and wanted to investigate further on it. Here's the code:

package com;

class Change {

    long coin2 = 0, bill5 = 0, bill10 = 0;
}

public class Test {

    static Change c = new Change();

    public static void main(String[] args) {
        Change m = optimalChange(19L);

        if(m == null){
            System.out.println("no change possible ...");
            return;
        }
        
        System.out.println("Coin  2E: " + m.coin2);
        System.out.println("bill  5E: " + m.bill5);
        System.out.println("bill 10E: " + m.bill10);

        long result = m.coin2 * 2 + m.bill5 * 5 + m.bill10 * 10;

        System.out.println("Change given: " + result);
    }

    static Change optimalChange(long s) {

        if (s < 2) {
            return s == 0 ? c : null;
        } else if (s < 5) {
            c.coin2++;
            return optimalChange(s - 2);
        } else if (s < 10) {
            c.bill5++;
            return optimalChange(s - 5);
        } else {
            c.bill10++;
            return optimalChange(s - 10);
        }

    }

}

推荐答案

您正在寻找的是最少量的账单.

What you are looking for is the most minimal amount of bills possible.

动态编程方法将是一种更理想的方法.

The Dynamic-Programming approach would be a more optimal approach for this.

时间复杂度= O(金钱* |硬币|)

让我们

硬币 = {c1，c2，c3，... cN} =>可用于进行更改的硬币组

Coins = {c1, c2, c3, ... cN} => Set of coins that can be used to make change

钱 =获得零钱所需的金额

Money = Amount of money required to get change for

D [i] [j] =表示使用 set = {c1，c2 ...cj}

这是工作代码(代码在Python中，但很容易转移到Java):

Here is the working code (code is in Python, but easily transferrable to Java):

Coins = [2, 5, 10]
Money = 99

D = [[100000000 for j in range(len(Coins))] for i in range(Money + 1)]

for i in range(1, Money + 1):
    for j in range(len(Coins)):
        if j > 0:
            D[i][j] = D[i][j-1]
        if i == Coins[j]:
            D[i][j] = min(D[i][j], 1)
        elif i > Coins[j] and D[i - Coins[j]][j] > 0:
            D[i][j] = min(1 + D[i - Coins[j]][j], D[i][j])


print (D[-1][-1])

输出:

12

这篇关于是否有针对此货币兑换问题的最佳解决方案?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！