是否有针对此货币兑换问题的最佳解决方案? [英] 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屋!