1에서 99 센트까지 변경할 수있는 최소한의 코인 수를 찾습니다.
최근에 동료에게이 문제를 해결하기위한 알고리즘을 작성하도록 요청했습니다.
1에서 99 센트까지 변경할 수있는 최소한의 동전 수를 찾으십시오. 동전은 페니 (1), 니켈 (5), 다임 (10), 분기 (25)로만 가능하며 해당 동전을 사용하여 1에서 99까지 (1 센트 단위로) 모든 값을 만들 수 있어야합니다.
그러나 가능한 모든 동전 조합을 검토하지 않고는 실제로 이것을 수행하는 방법을 실제로 알지 못한다는 것을 깨달았습니다. 이 문제를 해결하는 더 좋은 방법이 있어야하지만,이 유형의 알고리즘에 대한 일반적인 이름이 무엇인지 알 수 없으며 모든 솔루션을 보는 것 이상으로 단순화하는 방법을 알아낼 수 없습니다.
누군가 저를 올바른 방향으로 안내하거나 더 효율적인 알고리즘을 제공 할 수 있는지 궁금합니다.
당신이 찾고있는 것은 동적 프로그래밍 입니다.
이전 답변 위에 작성할 수 있으므로 가능한 모든 값에 대해 가능한 모든 조합을 실제로 열거 할 필요는 없습니다.
알고리즘은 2 개의 매개 변수를 가져야합니다.
- 가능한 코인 가치 목록, 여기
[1, 5, 10, 25] - 커버 할 범위, 여기
[1, 99]
그리고 목표는이 범위에 필요한 최소한의 동전 세트를 계산하는 것입니다.
가장 간단한 방법은 상향식으로 진행하는 것입니다.
Range Number of coins (in the minimal set)
1 5 10 25
[1,1] 1
[1,2] 2
[1,3] 3
[1,4] 4
[1,5] 5
[1,5]* 4 1 * two solutions here
[1,6] 4 1
[1,9] 4 1
[1,10] 5 1 * experience tells us it's not the most viable one :p
[1,10] 4 2 * not so viable either
[1,10] 4 1 1
[1,11] 4 1 1
[1,19] 4 1 1
[1,20] 5 1 1 * not viable (in the long run)
[1,20] 4 2 1 * not viable (in the long run)
[1,20] 4 1 2
각 단계에서 최대 하나의 코인을 추가하여 진행할 수 있으며, 위치 만 알면됩니다. 이는 범위 [x,y]가에 포함되어 [x,y+1]있으므로에 대한 최소 집합에에 대한 최소 집합 [x,y+1]이 포함되어야 한다는 사실로 귀결됩니다 [x,y].
당신이 알아 차렸을지도 모르지만, 때로는 결정이없는 경우가 있습니다. 즉, 여러 세트에 동일한 수의 코인이 있습니다. 이 경우 어느 것을 버려야할지 나중에 결정할 수 있습니다.
동전을 추가하면 일반적으로 추가 한 것보다 훨씬 더 큰 범위를 커버 할 수 있다는 것을 알면 실행 시간을 향상시킬 수 있어야합니다.
예를 들어 다음 사항에 유의하십시오.
[1,5] 4*1 1*5
[1,9] 4*1 1*5
우리는 덮기 위해 니켈을 추가 [1,5]하지만 이것은 우리에게 [1,9]무료로 제공합니다!
그러나 다루기 위해 터무니없는 입력 세트 [2,3,5,10,25]를 다룰 [2,99]때 새 세트에서 다루는 범위를 빠르게 확인하는 방법이 확실하지 않거나 실제로 더 효율적입니다.
상한선을 매우 빠르게 찾을 수 있습니다.
당신은 3/4를 취합니다. 그런 다음 '갭'1-24, 26-49, 51-74, 76-99 만 다른 동전으로 채워야합니다.
사소하게, 그것은 2 개의 다임, 1 개의 니켈, 4 개의 동전으로 작동 할 것입니다.
따라서 3 + 4 + 2 + 1은 코인 수의 상한이되어야합니다. 무차별 대입 알고리즘이 thta를 초과 할 때마다 더 깊은 검색을 즉시 중지 할 수 있습니다.
나머지 검색은 동적 프로그래밍을 사용하여 어떤 용도로든 충분히 빠르게 수행되어야합니다.
(편집 : Gabe의 관찰에 따라 정답)
거스름돈으로 4 개를 받고 싶기 때문에 최소 4 페니가 필요하며, 동전으로 만 할 수 있습니다.
동전이 4 개 이상있는 것은 최적이 아닙니다. 4 + x 페니 대신에 4 페니와 x 니켈을 가질 수 있습니다-적어도 같은 범위에 걸쳐 있습니다.
따라서 정확히 4 페니가 있습니다.
잔돈으로 5 개를 받으려면 니켈이 1 개 이상 필요합니다.
니켈이 1 개 이상있는 것은 최적이 아닙니다. 1 + x 니켈 대신 니켈 1 개와 다임 x 1 개를 가질 수 있습니다. 적어도 동일한 범위에 걸쳐 있습니다.
따라서 정확히 1 니켈이 있습니다.
20 개를 얻고 싶기 때문에 최소 2 개의 다임이 필요합니다.
이것은 당신이 동전 4 개, 니켈 1 개, 최소 2 개를 가지고 있음을 의미합니다.
동전이 10 개 미만이면 3 쿼터 미만일 것입니다. 그러나 모든 동전을 사용하여 얻을 수있는 최대 가능한 변화는 4 + 5 + 20 + 50 = 79로 충분하지 않습니다.
이것은 적어도 10 개의 코인이 있음을 의미합니다. Thomas의 대답 은 사실 당신이 동전 4 개, 니켈 1 개, 다임 2 개, 3 쿼터를 가지고 있다면 모두 괜찮다는 것을 보여줍니다.
저는 오늘 동적 프로그래밍 에 대해 배웠 으며 그 결과는 다음과 같습니다.
coins = [1,5,10,25]
d = {} # stores tuples of the form (# of coins, [coin list])
# finds the minimum # of coins needed to
# make change for some number of cents
def m(cents):
if cents in d.keys():
return d[cents]
elif cents > 0:
choices = [(m(cents - x)[0] + 1, m(cents - x)[1] + [x]) for x in coins if cents >= x]
# given a list of tuples, python's min function
# uses the first element of each tuple for comparison
d[cents] = min(choices)
return d[cents]
else:
d[0] = (0, [])
return d[0]
for x in range(1, 100):
val = m(x)
print x, "cents requires", val[0], "coins:", val[1]
동적 프로그래밍은 정말 마술입니다.
좋은 질문. 이것이 제가 생각 해낸 논리입니다. 25 개를 포함한 몇 가지 시나리오로 테스트되었습니다.
class Program
{
//Allowable denominations
const int penny = 1;
const int nickel = 5;
const int dime = 10;
const int quarter = 25;
const int maxCurrencyLevelForTest =55; //1-n where n<=99
static void Main(string[] args)
{
int minPenniesNeeded = 0;
int minNickelsNeeded = 0;
int minDimesNeeded = 0;
int minQuartersNeeded = 0;
if (maxCurrencyLevelForTest == penny)
{
minPenniesNeeded = 1;
}
else if (maxCurrencyLevelForTest < nickel)
{
minPenniesNeeded = MinCountNeeded(penny, maxCurrencyLevelForTest);
}
else if (maxCurrencyLevelForTest < dime)
{
minPenniesNeeded = MinCountNeeded(penny, nickel - 1);
minNickelsNeeded = MinCountNeeded(nickel, maxCurrencyLevelForTest);
}
else if (maxCurrencyLevelForTest < quarter)
{
minPenniesNeeded = MinCountNeeded(penny, nickel - 1);
minNickelsNeeded = MinCountNeeded(nickel, dime - 1);
minDimesNeeded = MinCountNeeded(dime, maxCurrencyLevelForTest);
}
else
{
minPenniesNeeded = MinCountNeeded(penny, nickel - 1);
minNickelsNeeded = MinCountNeeded(nickel, dime - 1);
minDimesNeeded = MinCountNeeded(dime, quarter - 1);
var maxPossilbleValueWithoutQuarters = (minPenniesNeeded * penny + minNickelsNeeded * nickel + minDimesNeeded * dime);
if (maxCurrencyLevelForTest > maxPossilbleValueWithoutQuarters)
{
minQuartersNeeded = (((maxCurrencyLevelForTest - maxPossilbleValueWithoutQuarters)-1) / quarter) + 1;
}
}
var minCoinsNeeded = minPenniesNeeded + minNickelsNeeded+minDimesNeeded+minQuartersNeeded;
Console.WriteLine(String.Format("Min Number of coins needed: {0}", minCoinsNeeded));
Console.WriteLine(String.Format("Penny: {0} needed", minPenniesNeeded));
Console.WriteLine(String.Format("Nickels: {0} needed", minNickelsNeeded));
Console.WriteLine(String.Format("Dimes: {0} needed", minDimesNeeded));
Console.WriteLine(String.Format("Quarters: {0} needed", minQuartersNeeded));
Console.ReadLine();
}
private static int MinCountNeeded(int denomination, int upperRange)
{
int remainder;
return System.Math.DivRem(upperRange, denomination,out remainder);
}
}
일부 결과 : maxCurrencyLevelForTest = 25 인 경우
Min Number of coins needed: 7
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 0 needed
maxCurrencyLevelForTest = 99 인 경우
Min Number of coins needed: 10
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 3 needed
maxCurrencyLevelForTest : 54
Min Number of coins needed: 8
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 1 needed
maxCurrencyLevelForTest : 55
Min Number of coins needed: 9
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 2 needed
maxCurrencyLevelForTest : 79
Min Number of coins needed: 9
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 2 needed
maxCurrencyLevelForTest : 85
Min Number of coins needed: 10
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 3 needed
코드는 더 리팩토링 될 수 있습니다.
편집 : 댓글 작성자가 언급했듯이 질문을 잘못 해석했습니다. (문제는 대학의 학생들이 풀어야하는 기본적인 CS 문제와 매우 유사합니다 ...) 손 을 흔들어보십시오. 이것은 당신이 찾고있는 답이 아닙니다. 즉, 원래 대답은 틀렸지 만 O ( n ) 솔루션 의 디딤돌로 사용할 수 있습니다 .
따라서 아래에서 잘못된 답을 선택하면 단일 값 (예 : 68 센트에 필요한 최소 주화)에 대해서만 해결되고 모든 값에 대해 실행됩니다.
changes = []
for amount in xrange(1, 100): # [1, 99]
changes.append( run_the_algo_below( amount ) )
# Take the maximum for each coin type.
# ie, if run_the_algo_below returns (q, d, n, p):
change = [0, 0, 0, 0]
for c in changes:
change = [max(c[i], change[i] for i in xrange(0, 4)]
자, 이것은 확실히 당신에게 유효한 대답을 줄 것이지만 최소한의 대답입니까? (이것이 더 어려운 부분입니다. 현재 제 직감이 예라고 말하지만, 저는 여전히 이것에 대해 생각하고 있습니다 ...)
( 오답 )
와. 루프? 동적 프로그래밍? 정말 여러분?
Python에서 :
amount = ( your_amount_in_cents )
quarters = amount // 25
dimes = amount % 25 // 10
nickels = amount % 25 % 10 // 5
pennies = amount % 25 % 10 % 5
아마도 이러한 모듈로 연산 중 일부는 단순화 될 수 있습니다.
어렵지 않습니다. 실생활에서 어떻게 변화를 일으키는 지 생각하면됩니다. 다른 분기를 추가하면 원하는 금액을 초과 할 때까지 분기를 제공하고, 다른 1 센트를 추가하면 원하는 금액을 초과 할 때까지 10 센트를 제공합니다. 그런 다음 모듈로 및 나눗셈과 같은 수학 연산으로 변환합니다. 동일한 솔루션이 달러에 적용되며 초를 HH : MM : SS 등으로 변환합니다.
미국 통화에 대해 이야기한다고 가정하면 욕심 많은 알고리즘이 필요합니다. http://en.wikipedia.org/wiki/Greedy_algorithm
본질적으로, 당신은 가장 높은 것부터 낮은 것까지 모든 교단을 시도하고, 아무것도 남지 않을 때까지 가능한 한 많은 동전을 가져옵니다.
일반적인 경우 http://en.wikipedia.org/wiki/Change-making_problem을 참조하십시오 . 욕심 많은 알고리즘이 작동하지 않는 임의의 교단에 대한 답을 찾기 위해 동적 프로그래밍 또는 선형 프로그래밍을 사용하고 싶기 때문입니다.
PHP에서 이러한 유형의 문제에 대한 좋은 해결책을 찾지 못한 후이 함수를 개발했습니다.
금액에 관계없이 (최대 $ 999.99) 해당 값에 도달하는 데 필요한 각 지폐 / 코인의 최소 수의 배열을 반환합니다.
먼저 값을 int로 변환합니다 (어떤 이유로 표준 부동 값을 사용할 때 맨 끝에 오류가 발생합니다).
반환 된 액면가도 동전 단위입니다 (예 : 5000 = $ 50, 100 = $ 1 등).
function makeChange($val)
{
$amountOfMoney = intval($val*100);
$cashInPennies = array(10000,5000,2000,1000,500,100,25,10,5,1);
$outputArray = array();
$currentSum = 0;
$currentDenom = 0;
while ($currentSum < $amountOfMoney) {
if( ( $currentSum + $cashInPennies[$currentDenom] ) <= $amountOfMoney ) {
$currentSum = $currentSum + $cashInPennies[$currentDenom];
$outputArray[$cashInPennies[$currentDenom]]++;
} else {
$currentDenom++;
}
}
return $outputArray;
}
$change = 56.93;
$output = makeChange($change);
print_r($output);
echo "<br>Total number of bills & coins: ".array_sum($output);
=== OUTPUT ===
Array ( [5000] => 1 [500] => 1 [100] => 1 [25] => 3 [10] => 1 [5] => 1 [1] => 3 )
Total number of bills & coins: 11
이것은 C #의 일반적인 솔루션 일 수 있습니다.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace CoinProblem
{
class Program
{
static void Main(string[] args)
{
var coins = new int[] { 1, 5, 10, 25 }; // sorted lowest to highest
int upperBound = 99;
int numCoinsRequired = upperBound / coins.Last();
for (int i = coins.Length - 1; i > 0; --i)
{
numCoinsRequired += coins[i] / coins[i - 1] - (coins[i] % coins[i - 1] == 0 ? 1 : 0);
}
Console.WriteLine(numCoinsRequired);
Console.ReadLine();
}
}
}
충분히 생각하지 못했습니다 ... 너무 늦은 밤입니다. 이 경우 답은 9가되어야한다고 생각했지만 Gabe는 10이되어야한다고 말했습니다. 질문을 어떻게 해석 하느냐에 따라 다릅니다 ... 우리는 어떤 가치 <= X를 생성 할 수있는 최소 코인 수를 찾고 있는지, 아니면 최소 수의 코인을 사용하여 어떤 값 <= X를 생성 할 수있는 최소 코인 수를 찾고 있습니까? ? 예를 들어 ... 저는 우리가 니켈없이 9 개의 동전으로 어떤 가치도 만들 수 있다고 확신합니다. 그러나 9를 생산하려면 ... 당신이 필요합니다 ... 오 ... 알겠습니다. 우리가 선택한 것이 아니기 때문에 당신은 가지고 있지 않은 9 페니가 필요할 것입니다. 이 경우에는 이 대답이 옳다고 생각 합니다. Thomas의 아이디어를 재귀 적으로 구현 한 것입니다.하지만 그가 왜 거기서 멈췄는지 모르겠습니다.
편집 : 이것은 잘못되었습니다.
작업
Find the least number of coins required, that can make any change from 1 to 99 cent.
과제와 다르다
For each single change from 1 to 99 cent, find the least number of coins required.
솔루션은 완전히 다른 동전 집합 일 수 있기 때문입니다.
(1), (5), (10), (25) 센트 동전이 없지만 (1), (3), (5), (17) 센트 동전이 있다고 가정합니다. 동전 하나만 필요합니다. 그러나 1에서 5까지의 모든 변경에는 동전 2 개와 동전 1 개가 필요합니다.
탐욕 알고리즘은 변경 값 및 동전 값과 관련하여 가장 작은 값에서 가장 큰 값으로 반복합니다.
With 1x(1) you get all change values below 2.
To make a change of 2, you need an additional coin,
which could have any value up to 2;
choose greedy -> choose the largest -> (1).
With 2x(1) you get all change values below 3.
To make a change of 3, you need an additional coin,
which could have any value up to 3;
choose greedy -> choose the largest -> (3).
With 2x(1)+1x(3) you get all change values below 6.
To make a change of 6, you need an additional coin,
which could have any value up to 6;
choose greedy -> choose the largest -> (5).
and so on...
그것은 Haskell에 있습니다.
coinsforchange [1,3,5,17] 99
where
coinsforchange coins change =
let f (coinssofar::[Int],sumsofar::Int) (largestcoin::Int,wanttogoto::Int) =
let coincount=(max 0 (wanttogoto-sumsofar+largestcoin-1))`div`largestcoin
in (replicate coincount largestcoin++coinssofar,sumsofar+coincount*largestcoin)
in foldl f ([],0) $ zip coins $ tail [c-1|c<-coins] ++ [change]
그리고 C ++에서 :
void f(std::map<unsigned,int> &coinssofar,int &sumsofar, unsigned largestcoin, int wanttogoto)
{
int x = wanttogoto - sumsofar + largestcoin - 1;
coinssofar[largestcoin] = (x>0) ? (x / largestcoin) : 0;
//returns coinssofar and sumsofar;
}
std::map<unsigned,int> coinsforchange(const std::list<unsigned> &coins, int change)
{
std::map<unsigned,int> coinssofar;
int sumsofar=0;
std::list<unsigned>::const_iterator coin = coins.begin();
unsigned largestcoin = *coin;
for( ++coin ; coin!=coins.end() ; largestcoin=*(coin++))
f(coinssofar,sumsofar,largestcoin,(*coin) - 1);
f(coinssofar,sumsofar,largestcoin,change);
return coinssofar;
}
일반적으로 코인이 COIN []이고 "변경 범위"1..MAX가있는 경우 다음은 최대 코인 수를 찾습니다.
Initialise array CHANGEVAL[MAX] to -1
For each element coin in COIN:
set CHANGEVAL[coin] to 1
Until there are no more -1 in CHANGEVAL:
For each index I over CHANGEVAL:
if CHANGEVAL[I] != -1:
let coincount = CHANGEVAL[I]
For each element coin in COIN:
let sum = coin + I
if (COINS[sum]=-1) OR ((coincount+1)<COINS[sum]):
COINS[sum]=coincount+1
엄밀히 말하면 내부 조건부에서 동전의 최소 성 검사가 필요한지 모르겠습니다. 나는 최소한의 동전 추가 체인이 정확하지만 후회하는 것보다 더 안전하다고 생각합니다.
VB 버전
Public Class Form1
Private Sub Button1_Click(ByVal sender As System.Object, _
ByVal e As System.EventArgs) Handles Button1.Click
For saleAMT As Decimal = 0.01D To 0.99D Step 0.01D
Dim foo As New CashDrawer(0, 0, 0)
Dim chg As List(Of Money) = foo.MakeChange(saleAMT, 1D)
Dim t As Decimal = 1 - saleAMT
Debug.WriteLine(t.ToString("C2"))
For Each c As Money In chg
Debug.WriteLine(String.Format("{0} of {1}", c.Count.ToString("N0"), c.moneyValue.ToString("C2")))
Next
Next
End Sub
Class CashDrawer
Private _drawer As List(Of Money)
Public Sub New(Optional ByVal QTYtwoD As Integer = -1, _
Optional ByVal QTYoneD As Integer = -1, _
Optional ByVal QTYfifty As Integer = -1, _
Optional ByVal QTYquarters As Integer = -1, _
Optional ByVal QTYdimes As Integer = -1, _
Optional ByVal QTYnickels As Integer = -1, _
Optional ByVal QTYpennies As Integer = -1)
_drawer = New List(Of Money)
_drawer.Add(New Money(2D, QTYtwoD))
_drawer.Add(New Money(1D, QTYoneD))
_drawer.Add(New Money(0.5D, QTYfifty))
_drawer.Add(New Money(0.25D, QTYquarters))
_drawer.Add(New Money(0.1D, QTYdimes))
_drawer.Add(New Money(0.05D, QTYnickels))
_drawer.Add(New Money(0.01D, QTYpennies))
End Sub
Public Function MakeChange(ByVal SaleAmt As Decimal, _
ByVal amountTendered As Decimal) As List(Of Money)
Dim change As Decimal = amountTendered - SaleAmt
Dim rv As New List(Of Money)
For Each c As Money In Me._drawer
change -= (c.NumberOf(change) * c.moneyValue)
If c.Count > 0 Then
rv.Add(c)
End If
Next
If change <> 0D Then Throw New ArithmeticException
Return rv
End Function
End Class
Class Money
'-1 equals unlimited qty
Private _qty As Decimal 'quantity in drawer
Private _value As Decimal 'value money
Private _count As Decimal = 0D
Public Sub New(ByVal theValue As Decimal, _
ByVal theQTY As Decimal)
Me._value = theValue
Me._qty = theQTY
End Sub
ReadOnly Property moneyValue As Decimal
Get
Return Me._value
End Get
End Property
Public Function NumberOf(ByVal theAmount As Decimal) As Decimal
If (Me._qty > 0 OrElse Me._qty = -1) AndAlso Me._value <= theAmount Then
Dim ct As Decimal = Math.Floor(theAmount / Me._value)
If Me._qty <> -1D Then 'qty?
'limited qty
If ct > Me._qty Then 'enough
'no
Me._count = Me._qty
Me._qty = 0D
Else
'yes
Me._count = ct
Me._qty -= ct
End If
Else
'unlimited qty
Me._count = ct
End If
End If
Return Me._count
End Function
ReadOnly Property Count As Decimal
Get
Return Me._count
End Get
End Property
End Class
End Class
다음은 Python의 간단한 버전입니다.
#!/usr/bin/env python
required = []
coins = [25, 10, 5, 1]
t = []
for i in range(1, 100):
while sum(t) != i:
for c in coins:
if sum(t) + c <= i:
t.append(c)
break
for c in coins:
while t.count(c) > required.count(c):
required.append(c)
del t[:]
print required
실행되면 다음을 stdout에 인쇄합니다.
[1, 1, 1, 1, 5, 10, 10, 25, 25, 25]
코드는 꽤 자명하지만 (Python에게 감사합니다!), 기본적으로 알고리즘은 현재 총 금액을 초과하지 않는 사용 가능한 가장 큰 동전을 임시 동전 목록에 추가하는 것입니다 (이 경우에는 ). 특정 총계에 대해 가장 효율적인 코인 세트를 찾으면 필요한 목록에 각 코인이 적어도 그 이상 있는지 확인하십시오. 1 ~ 99 센트의 모든 합계에 대해 그렇게하면 완료됩니다.
DP와 비슷한 종류의 문제에 대해이 알고리즘을 작성했습니다.
public class MinimumCoinProblem {
private static void calculateMinumCoins(int[] array_Coins, int sum) {
int[] array_best = new int[sum];
for (int i = 0; i < sum; i++) {
for (int j = 0; j < array_Coins.length; j++) {
if (array_Coins[j] <= i && (array_best[i] == 0 || (array_best[i - array_Coins[j]] + 1) <= array_best[i])) {
array_best[i] = array_best[i - array_Coins[j]] + 1;
}
}
}
System.err.println("The Value is" + array_best[14]);
}
public static void main(String[] args) {
int[] sequence1 = {11, 9,1, 3, 5,2 ,20};
int sum = 30;
calculateMinumCoins(sequence1, sum);
}
}
여기에 내 솔루션이 있습니다. 다시 Python으로 동적 프로그래밍을 사용합니다. 먼저 1..99 범위의 각 금액에 대해 변경하는 데 필요한 최소 코인 시퀀스를 생성하고 그 결과에서 각 교단에서 필요한 최대 코인 수를 찾습니다.
def min_any_change():
V, C = [1, 5, 10, 25], 99
mxP, mxN, mxD, mxQ = 0, 0, 0, 0
solution = min_change_table(V, C)
for i in xrange(1, C+1):
cP, cN, cD, cQ = 0, 0, 0, 0
while i:
coin = V[solution[i]]
if coin == 1:
cP += 1
elif coin == 5:
cN += 1
elif coin == 10:
cD += 1
else:
cQ += 1
i -= coin
if cP > mxP:
mxP = cP
if cN > mxN:
mxN = cN
if cD > mxD:
mxD = cD
if cQ > mxQ:
mxQ = cQ
return {'pennies':mxP, 'nickels':mxN, 'dimes':mxD, 'quarters':mxQ}
def min_change_table(V, C):
m, n, minIdx = C+1, len(V), 0
table, solution = [0] * m, [0] * m
for i in xrange(1, m):
minNum = float('inf')
for j in xrange(n):
if V[j] <= i and 1 + table[i - V[j]] < minNum:
minNum = 1 + table[i - V[j]]
minIdx = j
table[i] = minNum
solution[i] = minIdx
return solution
실행 min_any_change()하면 우리가 찾던 답이 나옵니다 {'pennies': 4, 'nickels': 1, 'dimes': 2, 'quarters': 3}. 테스트로, 우리는 어떤 종류의 동전을 제거하고 1..99 범위의 금액에 대해 여전히 변경이 가능한지 확인할 수 있습니다.
from itertools import combinations
def test(lst):
sums = all_sums(lst)
return all(i in sums for i in xrange(1, 100))
def all_sums(lst):
combs = []
for i in xrange(len(lst)+1):
combs += combinations(lst, i)
return set(sum(s) for s in combs)
위에서 얻은 결과를 테스트하면 다음을 얻습니다 True.
test([1, 1, 1, 1, 5, 10, 10, 25, 25, 25])
그러나 우리가 하나의 동전을 제거하면 어떤 교단이든 상관없이 False다음을 얻을 수 있습니다 .
test([1, 1, 1, 5, 10, 10, 25, 25, 25])
한편으로 이것은 대답되었습니다. 반면에 대부분의 답변에는 여러 줄의 코드가 필요합니다. 이 Python 답변에는 많은 줄의 코드가 필요하지 않습니다. ^ _ ^ :
div_round_up = lambda a, b: a // b if a % b == 0 else a // b + 1
def optimum_change(*coins):
wallet = [0 for i in range(0, len(coins) - 1)]
for j in range(0, len(wallet)):
target = coins[j + 1] - 1
target -= sum(wallet[i] * coins[i] for i in range(0, j))
wallet[j] = max(0, div_round_up(target, coins[j]))
return wallet
optimum_change(1, 5, 10, 25, 100)
# [4, 1, 2, 3]
이것은 내가 아직 고려하지 않은 입력에 대해 아마도 깨질 수있는 매우 간단한 크기 조정 알고리즘이지만 강력해야한다고 생각합니다. 기본적으로 "지갑에 새로운 유형의 동전을 추가하려면 다음 동전 유형 N을 살펴본 다음 만드는 데 필요한 새 동전의 양을 추가합니다 target = N - 1."라고 말합니다. 최소한 ceil((target - wallet_value)/coin_value)그렇게 해야한다고 계산하고 이것이 그 사이의 모든 숫자를 만들 것인지 확인하지 않습니다. 구문은 최종 숫자 "100"을 추가하여 "0에서 99 센트"를 인코딩합니다 target. 그러면 적절한 최종 .
확인하지 않는 이유는 "만약 할 수 있으면 자동으로 할 것입니다." 좀 더 직접적으로 말하면,이 단계를 페니 (값 1)에 대해 수행하면 알고리즘이 니켈 (값 5)을 임의의 하위 간격 0-4로 "분리"할 수 있습니다. 니켈에 대해 수행하면 이제 알고리즘이 "분리"할 수 있습니다. "10 센트 (값 10). 등등.
물론 이러한 특정 입력은 필요하지 않습니다. 이상한 통화도 사용할 수 있습니다.
>>> optimum_change(1, 4, 7, 8, 100)
[3, 1, 0, 12]
변경 사항으로 이미 8을 "파괴"할 수 있음을 알고 있기 때문에 7 동전을 자동으로 무시하는 방법에 유의하십시오.
https://www.coursera.org/course/bioinformatics 를 공부하는 동안 오늘 이것을 보았습니다.
DPCHANGE(money, coins)
MinNumCoins(0) ← 0
for m ← 1 to money
MinNumCoins(m) ← ∞
for i ← 1 to |coins|
if m ≥ coini
if MinNumCoins(m - coini) + 1 < MinNumCoins(m)
MinNumCoins(m) ← MinNumCoins(m - coini) + 1
output MinNumCoins(money)
쉼표로 구분 된 사용 가능한 교단 문자열과 목표 금액을 가져옵니다.
C # 구현 :
public static void DPCHANGE(int val, string denoms)
{
int[] idenoms = Array.ConvertAll(denoms.Split(','), int.Parse);
Array.Sort(idenoms);
int[] minNumCoins = new int[val + 1];
minNumCoins[0] = 0;
for (int m = 1; m <= val; m++)
{
minNumCoins[m] = Int32.MaxValue - 1;
for (int i = 1; i <= idenoms.Count() - 1; i++)
{
if (m >= idenoms[i])
{
if (minNumCoins[m - idenoms[i]] + 1 < minNumCoins[m])
{
minNumCoins[m] = minNumCoins[m - idenoms[i]] + 1;
}
}
}
}
}
내가 이해했듯이 표준 통화 시스템 값을 사용하는 경우 단일 루프로 최소 동전 수를 계산하는 것이 매우 쉽습니다. 항상 최대 코인 가치를 소비하고 가능하지 않으면 다음 옵션을 확인하십시오. 그러나 1,2,3,4와 같은 동전이있는 것과 같은 시스템이 있으면 작동하지 않습니다. 나는 동전을 1,2,5,10,25로 갖는 모든 아이디어는 인간이 쉽게 계산할 수 있도록하는 것이라고 생각합니다.
여기 내 생각입니다. 한 가지 흥미로운 점은 coin_with_max_value (이 경우 25 개)-1 개만 형성하는 데 필요한 최소 코인을 확인해야한다는 것입니다. 그 후이 최소 동전의 합계를 계산하십시오. 그 시점부터 우리는 총 비용과 알아 낸 합계의 차이에 따라 총 비용까지 임의의 수를 형성하기 위해 특정 수의 coin_with_max_value를 추가하면됩니다. 그게 다야.
따라서 우리가 가지고있는 값에 대해 24 분의 최소 동전이 발견되면 [1, 2, 2, 5, 10, 10]. 30 (최소 코인의 합)을 초과하는 25 개의 값마다 25 개의 코인을 계속 추가하면됩니다. 99에 대한 최종 답 :
[1, 2, 2, 5, 10, 10, 25, 25, 25]
9
import itertools
import math
def ByCurrentCoins(val, coins):
for i in range(1, len(coins) + 1):
combinations = itertools.combinations(coins, i)
for combination in combinations:
if sum(combination) == val:
return True
return False
def ExtraCoin(val, all_coins, curr_coins):
for c in all_coins:
if ByCurrentCoins(val, curr_coins + [c]):
return c
def main():
cost = 99
coins = sorted([1, 2, 5, 10, 25], reverse=True)
max_coin = coins[0]
curr_coins = []
for c in range(1, min(max_coin, cost+1)):
if ByCurrentCoins(c, curr_coins):
continue
extra_coin = ExtraCoin(c, coins, curr_coins)
if not extra_coin:
print -1
return
curr_coins.append(extra_coin)
curr_sum = sum(curr_coins)
if cost > curr_sum:
extra_max_coins = int(math.ceil((cost - curr_sum)/float(max_coin)))
curr_coins.extend([max_coin for _ in range(extra_max_coins)])
print curr_coins
print len(curr_coins)
이 문제에 대해 Greedy 접근 방식은 DP 또는 다른 것보다 더 나은 솔루션을 제공합니다. 탐욕스러운 접근 방식 : 필요한 가치보다 작은 가장 큰 액면가를 찾아 전달할 코인 세트에 추가합니다. 방금 추가 한 금액만큼 필요한 센트를 낮추고 필요한 센트가 0이 될 때까지 반복합니다.
자바 솔루션의 내 솔루션 (욕심 많은 접근 방식) :
public class MinimumCoinDenomination {
private static final int[] coinsDenominations = {1, 5, 10, 25, 50, 100};
public static Map<Integer, Integer> giveCoins(int requiredCents) {
if(requiredCents <= 0) {
return null;
}
Map<Integer, Integer> denominations = new HashMap<Integer, Integer>();
int dollar = requiredCents/100;
if(dollar>0) {
denominations.put(100, dollar);
}
requiredCents = requiredCents - (dollar * 100);
//int sum = 0;
while(requiredCents > 0) {
for(int i = 1; i<coinsDenominations.length; i++) {
if(requiredCents < coinsDenominations[i]) {
//sum = sum +coinsDenominations[i-1];
if(denominations.containsKey(coinsDenominations[i-1])) {
int c = denominations.get(coinsDenominations[i-1]);
denominations.put(coinsDenominations[i-1], c+1);
} else {
denominations.put(coinsDenominations[i-1], 1);
}
requiredCents = requiredCents - coinsDenominations[i-1];
break;
}
}
}
return denominations;
}
public static void main(String[] args) {
System.out.println(giveCoins(199));
}
}
예제 프로그램 :
#include<stdio.h>
#define LEN 9 // array length
int main(){
int coins[LEN]={0,0,0,0,0,0,0,0,0}; // coin count
int cointypes[LEN]={1000,500,100,50,20,10,5,2,1}; // declare your coins and note here {ASC order}
int sum =0; //temp variable for sum
int inc=0; // for loop
int amount=0; // for total amount
printf("Enter Amount :");
scanf("%d",&amount);
while(sum<amount){
if((sum+cointypes[inc])<=amount){
sum = sum+ cointypes[inc];
//printf("%d[1] - %d\n",cointypes[inc],sum);
//switch case to count number of notes and coin
switch(cointypes[inc]){
case 1000:
coins[0]++;
break;
case 500:
coins[1]++;
break;
case 100:
coins[2]++;
break;
case 50:
coins[3]++;
break;
case 20:
coins[4]++;
break;
case 10:
coins[5]++;
break;
case 5:
coins[6]++;
break;
case 2:
coins[7]++;
break;
case 1:
coins[8]++;
break;
}
}else{
inc++;
}
}
printf("note for %d in\n note 1000 * %d\n note 500 * %d\n note 100 * %d\n note 50 * %d\n note 20 * %d\n note 10 * %d\n coin 5 * %d\n coin 2 * %d\n coin 1 * %d\n",amount,coins[0],coins[1],coins[2],coins[3],coins[4],coins[5],coins[6],coins[7],coins[8]);
}
다음은 Linq를 사용하는 간단한 C # 솔루션입니다.
internal class Program
{
public static IEnumerable<Coin> Coins = new List<Coin>
{
new Coin {Name = "Dime", Value = 10},
new Coin {Name = "Penny", Value = 1},
new Coin {Name = "Nickel", Value = 5},
new Coin {Name = "Quarter", Value = 25}
};
private static void Main(string[] args)
{
PrintChange(34);
Console.ReadKey();
}
public static void PrintChange(int amount)
{
decimal remaining = amount;
//Order coins by value in descending order
var coinsDescending = Coins.OrderByDescending(v => v.Value);
foreach (var coin in coinsDescending)
{
//Continue to smaller coin when current is larger than remainder
if (remaining < coin.Value) continue;
// Get # of coins that fit in remaining amount
var quotient = (int)(remaining / coin.Value);
Console.WriteLine(new string('-',28));
Console.WriteLine("{0,10}{1,15}", coin.Name, quotient);
//Subtract fitting coins from remaining amount
remaining -= quotient * coin.Value;
if (remaining <= 0) break; //Exit when no remainder left
}
Console.WriteLine(new string('-', 28));
}
public class Coin
{
public string Name { get; set; }
public int Value { get; set; }
}
}
이것에서 영감 https://www.youtube.com/watch?v=GafjS0FfAC0 다음
영상에 도입 서브 문제 원리 겹치는 1) 최적 서브 문제 2)
using System;
using System.Collections.Generic;
using System.Linq;
namespace UnitTests.moneyChange
{
public class MoneyChangeCalc
{
private static int[] _coinTypes;
private Dictionary<int, int> _solutions;
public MoneyChangeCalc(int[] coinTypes)
{
_coinTypes = coinTypes;
Reset();
}
public int Minimun(int amount)
{
for (int i = 2; i <= amount; i++)
{
IList<int> candidates = FulfillCandidates(i);
try
{
_solutions.Add(i, candidates.Any() ? (candidates.Min() + 1) : 0);
}
catch (ArgumentException)
{
Console.WriteLine("key [{0}] = {1} already added", i, _solutions[i]);
}
}
int minimun2;
_solutions.TryGetValue(amount, out minimun2);
return minimun2;
}
internal IList<int> FulfillCandidates(int amount)
{
IList<int> candidates = new List<int>(3);
foreach (int coinType in _coinTypes)
{
int sub = amount - coinType;
if (sub < 0) continue;
int candidate;
if (_solutions.TryGetValue(sub, out candidate))
candidates.Add(candidate);
}
return candidates;
}
private void Reset()
{
_solutions = new Dictionary<int, int>
{
{0,0}, {_coinTypes[0] ,1}
};
}
}
}
테스트 사례 :
using NUnit.Framework;
using System.Collections;
namespace UnitTests.moneyChange
{
[TestFixture]
public class MoneyChangeTest
{
[TestCaseSource("TestCasesData")]
public int Test_minimun2(int amount, int[] coinTypes)
{
var moneyChangeCalc = new MoneyChangeCalc(coinTypes);
return moneyChangeCalc.Minimun(amount);
}
private static IEnumerable TestCasesData
{
get
{
yield return new TestCaseData(6, new[] { 1, 3, 4 }).Returns(2);
yield return new TestCaseData(3, new[] { 2, 4, 6 }).Returns(0);
yield return new TestCaseData(10, new[] { 1, 3, 4 }).Returns(3);
yield return new TestCaseData(100, new[] { 1, 5, 10, 20 }).Returns(5);
}
}
}
}
자바에서 탐욕스러운 접근 방식을 사용한 솔루션은 다음과 같습니다.
public class CoinChange {
public static void main(String args[]) {
int denominations[] = {1, 5, 10, 25};
System.out.println("Total required coins are " + greeadApproach(53, denominations));
}
public static int greeadApproach(int amount, int denominations[]) {
int cnt[] = new int[denominations.length];
for (int i = denominations.length-1; amount > 0 && i >= 0; i--) {
cnt[i] = (amount/denominations[i]);
amount -= cnt[i] * denominations[i];
}
int noOfCoins = 0;
for (int cntVal : cnt) {
noOfCoins+= cntVal;
}
return noOfCoins;
}
}
그러나 이것은 단일 금액으로 작동합니다. 범위에 대해 실행하려면 각 범위 양에 대해 호출해야합니다.
비슷한 답변이 몇 가지 있지만 Java를 사용한 솔루션은 이해하기가 좀 더 쉬워 보입니다. 이것 좀 봐.
public static int findMinimumNumberOfCoins(int inputCents) {
// Error Check, If the input is 0 or lower, return 0.
if(inputCents <= 0) return 0;
// Create the List of Coins that We need to loop through. Start from highest to lowewst.
// 25-10-5-1
int[] mCoinsArray = getCoinsArray();
// Number of Total Coins.
int totalNumberOfCoins = 0;
for(int i=0; i < mCoinsArray.length; i++) {
// Get the Coin from Array.
int coin = mCoinsArray[i];
// If there is no inputCoin Left, simply break the for-loop
if(inputCents == 0) break;
// Check If we have a smaller input than our coin
// If it's, we need to go the Next one in our Coins Array.
// e.g, if we have 8, but the current index of array is 10, we need to go to 5.
if(inputCents < coin) continue;
int quotient = inputCents/coin;
int remainder = inputCents%coin;
// Add qutient to number of total coins.
totalNumberOfCoins += quotient;
// Update the input with Remainder.
inputCents = remainder;
}
return totalNumberOfCoins;
}
// Create a Coins Array, from 25 to 1. Highest is first.
public static int[] getCoinsArray() {
int[] mCoinsArray = new int[4];
mCoinsArray[0] = 25;
mCoinsArray[1] = 10;
mCoinsArray[2] = 5;
mCoinsArray[3] = 1;
return mCoinsArray;
}
이것은 해결책을 찾는 C #의 코드입니다.
public struct CoinCount
{
public int coinValue;
public int noOfCoins;
}
/// <summary>
/// Find and returns the no of coins in each coins in coinSet
/// </summary>
/// <param name="coinSet">sorted coins value in assending order</param>
/// <returns></returns>
public CoinCount[] FindCoinsCountFor1to99Collection(int[] coinSet)
{
// Add extra coin value 100 in the coin set. Since it need to find the collection upto 99.
CoinCount[] result = new CoinCount[coinSet.Length];
List<int> coinValues = new List<int>();
coinValues.AddRange(coinSet);
coinValues.Add(100);
// Selected coin total values
int totalCount = 0;
for (int i = 0; i < coinValues.Count - 1; i++)
{
int count = 0;
if (totalCount <= coinValues[i])
{
// Find the coins count
int remainValue = coinValues[i + 1] - totalCount;
count = (int)Math.Ceiling((remainValue * 1.0) / coinValues[i]);
}
else
{
if (totalCount <= coinValues[i + 1])
count = 1;
else
count = 0;
}
result[i] = new CoinCount() { coinValue = coinValues[i], noOfCoins = count };
totalCount += coinValues[i] * count;
}
return result;
}
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
public class LeastNumofCoins
{
public int getNumofCoins(int amount)
{
int denominations[]={50,25,10,5,2,1};
int numOfCoins=0;
int index=0;
while(amount>0)
{
int coin=denominations[index];
if(coin==amount)
{
numOfCoins++;
break;
}
if(coin<=amount)
{
amount=amount-coin;
numOfCoins++;
}
else
{
index++;
}
}
return numOfCoins;
}
public static void main(String[] args) throws IOException
{
Scanner scanner= new Scanner(new InputStreamReader(System.in));
System.out.println("Enter the Amount:");
int amoount=scanner.nextInt();
System.out.println("Number of minimum coins required to make "+ amoount +" is "+new LeastNumofCoins().getNumofCoins(amoount));
scanner.close();
}
}
'Nice programing' 카테고리의 다른 글
| "스레드 0x22c8이 코드 259 (0x103)와 함께 종료되었습니다."라는 메시지가 나타나는 이유는 무엇입니까? (0) | 2020.12.05 |
|---|---|
| Fat Arrow 클래스 메서드를 허용하도록 ESLint를 구성하는 방법 (0) | 2020.12.05 |
| 개인 세터 타이프 스크립트? (0) | 2020.12.05 |
| docker-compose.yml의 명명 된 볼륨에 대한 호스트 경로를 설정하는 방법 (0) | 2020.12.05 |
| Android의 (2D) 캔버스 드로잉 파이프 라인은 어떻게 서로 맞습니까? (0) | 2020.12.05 |