是否有针对此货币兑换问题的最佳解决方案?

本文介绍了是否有针对此货币兑换问题的最佳解决方案?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

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