我被要求创建一种方法,该方法将:
I was asked to create a method that would:
- 返回Change对象,如果没有可能的更改,则返回null
- 机器"有无限的账单:2、5和10
- 零钱对象必须返回尽可能少的账单
这是在codingame上提出的一个问题,希望对此进行进一步调查.这是代码:
This was a question asked in codingame 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更多推荐
是否有针对此货币兑换问题的最佳解决方案?
发布评论