반응형
달러 가치가 주어지면 동전의 모든 조합을 찾는 방법
몇 달 전에 인터뷰 준비를 위해 작성한 코드를 발견했습니다.
내가 가진 의견에 따르면이 문제를 해결하려고했습니다.
센트 단위의 달러 가치 (예 : 200 = 2 달러, 1000 = 10 달러)가 주어지면 달러 가치를 구성하는 동전의 모든 조합을 찾으십시오. 페니 (1 ¢), 니켈 (5 ¢), 다임 (10 ¢) 및 쿼터 (25 ¢) 만 허용됩니다.
예를 들어, 100이 주어진 경우 대답은 다음과 같아야합니다.
4 quarter(s) 0 dime(s) 0 nickel(s) 0 pennies
3 quarter(s) 1 dime(s) 0 nickel(s) 15 pennies
etc.
나는 이것이 반복적이고 재귀적인 방법으로 해결할 수 있다고 생각합니다. 내 재귀 솔루션은 매우 버그가 많으며 다른 사람들 이이 문제를 어떻게 해결할지 궁금합니다. 이 문제의 어려운 부분은 가능한 효율적으로 만드는 것이 었습니다.
나는 이것을 오래 전에 한 번 살펴 보았고 그것에 대한 나의 작은 글을 읽을 수 있습니다 . Mathematica 소스 는 다음과 같습니다 .
생성 함수를 사용하면 문제에 대한 닫힌 양식 상수 시간 솔루션을 얻을 수 있습니다. Graham, Knuth 및 Patashnik 's Concrete Mathematics 가 이에 대한 책이며 문제에 대한 상당히 광범위한 토론을 포함합니다. 본질적으로 n 번째 계수가 n 달러 를 변경하는 방법의 수인 다항식을 정의합니다 .
이 글의 4-5 페이지는 Mathematica (또는 다른 편리한 컴퓨터 대수 시스템)를 사용하여 3 줄의 코드로 몇 초 만에 10 ^ 10 ^ 6 달러의 답을 계산하는 방법을 보여줍니다.
(그리고 이것은 75Mhz Pentium에서 몇 초가 걸렸을 정도로 오래 전에 ...)
참고 : 여기에는 여러 가지 방법 만 표시됩니다.
스칼라 기능 :
def countChange(money: Int, coins: List[Int]): Int =
if (money == 0) 1
else if (coins.isEmpty || money < 0) 0
else countChange(money - coins.head, coins) + countChange(money, coins.tail)
재귀 솔루션을 선호합니다. 가장 작은 단위가 나머지 통화 금액을 균등하게 나눌 수 있다면 교단 목록이 있습니다.
기본적으로 당신은 가장 큰 교단에서 가장 작은 교단으로 이동합니다.
재귀 적으로
- 현재 채울 총액과 최대 액면가 (1 개 이상 남음)가 있습니다. 하나의 교파 만 남은 경우 총계를 채우는 한 가지 방법 만 있습니다. k * cur denomination <= total과 같이 현재 교파의 0-k 사본을 사용할 수 있습니다.
- 0에서 k의 경우 수정 된 총계 및 새로운 최대 명칭을 가진 함수를 호출하십시오.
- 0에서 k까지 결과를 더합니다. 현재 교단에서 총계를 채우는 방법은 여러 가지가 있습니다. 이 번호를 반환하십시오.
여기 내 문제의 파이썬 버전이 200 센트입니다. 나는 1463 방법을 얻는다. 이 버전은 모든 조합과 최종 수를 인쇄합니다.
#!/usr/bin/python
# find the number of ways to reach a total with the given number of combinations
cents = 200
denominations = [25, 10, 5, 1]
names = {25: "quarter(s)", 10: "dime(s)", 5 : "nickel(s)", 1 : "pennies"}
def count_combs(left, i, comb, add):
if add: comb.append(add)
if left == 0 or (i+1) == len(denominations):
if (i+1) == len(denominations) and left > 0:
if left % denominations[i]:
return 0
comb.append( (left/denominations[i], demoninations[i]) )
i += 1
while i < len(denominations):
comb.append( (0, denominations[i]) )
i += 1
print(" ".join("%d %s" % (n,names[c]) for (n,c) in comb))
return 1
cur = denominations[i]
return sum(count_combs(left-x*cur, i+1, comb[:], (x,cur)) for x in range(0, int(left/cur)+1))
count_combs(cents, 0, [], None)
스칼라 기능 :
def countChange(money: Int, coins: List[Int]): Int = {
def loop(money: Int, lcoins: List[Int], count: Int): Int = {
// if there are no more coins or if we run out of money ... return 0
if ( lcoins.isEmpty || money < 0) 0
else{
if (money == 0 ) count + 1
/* if the recursive subtraction leads to 0 money left - a prefect division hence return count +1 */
else
/* keep iterating ... sum over money and the rest of the coins and money - the first item and the full set of coins left*/
loop(money, lcoins.tail,count) + loop(money - lcoins.head,lcoins, count)
}
}
val x = loop(money, coins, 0)
Console println x
x
}
다음은 모든 조합을 보여달라고 요청한 문제를 해결하기위한 완전히 간단한 C ++ 코드입니다.
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
if (argc != 2)
{
printf("usage: change amount-in-cents\n");
return 1;
}
int total = atoi(argv[1]);
printf("quarter\tdime\tnickle\tpenny\tto make %d\n", total);
int combos = 0;
for (int q = 0; q <= total / 25; q++)
{
int total_less_q = total - q * 25;
for (int d = 0; d <= total_less_q / 10; d++)
{
int total_less_q_d = total_less_q - d * 10;
for (int n = 0; n <= total_less_q_d / 5; n++)
{
int p = total_less_q_d - n * 5;
printf("%d\t%d\t%d\t%d\n", q, d, n, p);
combos++;
}
}
}
printf("%d combinations\n", combos);
return 0;
}
그러나 조합 수를 계산하는 하위 문제에 대해서는 매우 흥미 롭습니다. 닫힌 형식의 방정식이 있다고 생각합니다.
하위 문제는 일반적인 동적 프로그래밍 문제입니다.
/* Q: Given some dollar value in cents (e.g. 200 = 2 dollars, 1000 = 10 dollars),
find the number of combinations of coins that make up the dollar value.
There are only penny, nickel, dime, and quarter.
(quarter = 25 cents, dime = 10 cents, nickel = 5 cents, penny = 1 cent) */
/* A:
Reference: http://andrew.neitsch.ca/publications/m496pres1.nb.pdf
f(n, k): number of ways of making change for n cents, using only the first
k+1 types of coins.
+- 0, n < 0 || k < 0
f(n, k) = |- 1, n == 0
+- f(n, k-1) + f(n-C[k], k), else
*/
#include <iostream>
#include <vector>
using namespace std;
int C[] = {1, 5, 10, 25};
// Recursive: very slow, O(2^n)
int f(int n, int k)
{
if (n < 0 || k < 0)
return 0;
if (n == 0)
return 1;
return f(n, k-1) + f(n-C[k], k);
}
// Non-recursive: fast, but still O(nk)
int f_NonRec(int n, int k)
{
vector<vector<int> > table(n+1, vector<int>(k+1, 1));
for (int i = 0; i <= n; ++i)
{
for (int j = 0; j <= k; ++j)
{
if (i < 0 || j < 0) // Impossible, for illustration purpose
{
table[i][j] = 0;
}
else if (i == 0 || j == 0) // Very Important
{
table[i][j] = 1;
}
else
{
// The recursion. Be careful with the vector boundary
table[i][j] = table[i][j-1] +
(i < C[j] ? 0 : table[i-C[j]][j]);
}
}
}
return table[n][k];
}
int main()
{
cout << f(100, 3) << ", " << f_NonRec(100, 3) << endl;
cout << f(200, 3) << ", " << f_NonRec(200, 3) << endl;
cout << f(1000, 3) << ", " << f_NonRec(1000, 3) << endl;
return 0;
}
이 코드는 Java를 사용하여이 문제를 해결하고 작동합니다.이 방법은 너무 많은 루프로 인해 좋은 아이디어는 아니지만 실제로는 간단합니다.
public class RepresentCents {
public static int sum(int n) {
int count = 0;
for (int i = 0; i <= n / 25; i++) {
for (int j = 0; j <= n / 10; j++) {
for (int k = 0; k <= n / 5; k++) {
for (int l = 0; l <= n; l++) {
int v = i * 25 + j * 10 + k * 5 + l;
if (v == n) {
count++;
} else if (v > n) {
break;
}
}
}
}
}
return count;
}
public static void main(String[] args) {
System.out.println(sum(100));
}
}
이것은 정말 오래된 질문이지만 다른 모든 것보다 작게 보이는 Java의 재귀 솔루션을 생각해 냈습니다.
public static void printAll(int ind, int[] denom,int N,int[] vals){
if(N==0){
System.out.println(Arrays.toString(vals));
return;
}
if(ind == (denom.length))return;
int currdenom = denom[ind];
for(int i=0;i<=(N/currdenom);i++){
vals[ind] = i;
printAll(ind+1,denom,N-i*currdenom,vals);
}
}
개량:
public static void printAllCents(int ind, int[] denom,int N,int[] vals){
if(N==0){
if(ind < denom.length) {
for(int i=ind;i<denom.length;i++)
vals[i] = 0;
}
System.out.println(Arrays.toString(vals));
return;
}
if(ind == (denom.length)) {
vals[ind-1] = 0;
return;
}
int currdenom = denom[ind];
for(int i=0;i<=(N/currdenom);i++){
vals[ind] = i;
printAllCents(ind+1,denom,N-i*currdenom,vals);
}
}
세트 J의 값을 사용하여 센트를 만드는 조합 세트 C (i, J)를 보자.
C를 다음과 같이 정의 할 수 있습니다.
(first (J)는 집합의 요소를 결정 론적으로 취 합니다)
그것은 꽤 재귀적인 기능으로 밝혀졌습니다 ... 메모를 사용하면 합리적으로 효율적입니다.)
고유 조합 문제를 해결하기위한 세미 핵-내림차순 강제 :
$ 데님 = [1,5,10,25]
데프 all_combs (sum, last)
sum == 0이면 1을 반환
$ denoms를 반환합니다 .select {| d | d & le sum && d & le last} .inject (0) {| total, denom |
total + all_combs (sum-denom, denom)}
종료
메모되지 않으므로 느리게 실행되지만 아이디어를 얻습니다.
# short and sweet with O(n) table memory
#include <iostream>
#include <vector>
int count( std::vector<int> s, int n )
{
std::vector<int> table(n+1,0);
table[0] = 1;
for ( auto& k : s )
for(int j=k; j<=n; ++j)
table[j] += table[j-k];
return table[n];
}
int main()
{
std::cout << count({25, 10, 5, 1}, 100) << std::endl;
return 0;
}
이것은 파이썬에서 내 대답입니다. 재귀를 사용하지 않습니다.
def crossprod (list1, list2):
output = 0
for i in range(0,len(list1)):
output += list1[i]*list2[i]
return output
def breakit(target, coins):
coinslimit = [(target / coins[i]) for i in range(0,len(coins))]
count = 0
temp = []
for i in range(0,len(coins)):
temp.append([j for j in range(0,coinslimit[i]+1)])
r=[[]]
for x in temp:
t = []
for y in x:
for i in r:
t.append(i+[y])
r = t
for targets in r:
if crossprod(targets, coins) == target:
print targets
count +=1
return count
if __name__ == "__main__":
coins = [25,10,5,1]
target = 78
print breakit(target, coins)
출력 예
...
1 ( 10 cents) 2 ( 5 cents) 58 ( 1 cents)
4 ( 5 cents) 58 ( 1 cents)
1 ( 10 cents) 1 ( 5 cents) 63 ( 1 cents)
3 ( 5 cents) 63 ( 1 cents)
1 ( 10 cents) 68 ( 1 cents)
2 ( 5 cents) 68 ( 1 cents)
1 ( 5 cents) 73 ( 1 cents)
78 ( 1 cents)
Number of solutions = 121
var countChange = function (money,coins) {
function countChangeSub(money,coins,n) {
if(money==0) return 1;
if(money<0 || coins.length ==n) return 0;
return countChangeSub(money-coins[n],coins,n) + countChangeSub(money,coins,n+1);
}
return countChangeSub(money,coins,0);
}
둘 다 : 모든 교파를 높음에서 낮음으로 반복하고, 교파 중 하나를 취하고, 총 요구량에서 빼고, 나머지 부분에서 되풀이합니다 (사용 가능한 교단이 현재 반복 값과 같거나 낮도록 제한).
통화 시스템에서 허용하는 경우 최고 가치의 통화로 시작하여 가능한 한 많은 동전을 사용 하는 간단한 탐욕스러운 알고리즘 입니다.
그렇지 않으면,이 문제는 본질적으로 배낭 문제 이기 때문에 최적의 솔루션을 신속하게 찾기 위해 동적 프로그래밍이 필요합니다 .
예를 들어, 통화 시스템에 동전이있는 경우 : {13, 8, 1}욕심 많은 솔루션은 24로 변경 {13, 8, 1, 1, 1}되지만 실제 최적 솔루션은{8, 8, 8}
편집 : 나는 우리가 달러를 변경하는 모든 방법을 나열하지 않고 최적으로 변경하고 있다고 생각했습니다. 최근 인터뷰에서 변경 방법을 물었으므로 질문을 읽기 전에 미리 뛰어 들었습니다.
나는 이것이 매우 오래된 질문이라는 것을 알고 있습니다. 나는 정답을 찾고 있었고 간단하고 만족스러운 것을 찾을 수 없었습니다. 시간이 좀 걸렸지 만 뭔가를 적을 수있었습니다.
function denomination(coins, original_amount){
var original_amount = original_amount;
var original_best = [ ];
for(var i=0;i<coins.length; i++){
var amount = original_amount;
var best = [ ];
var tempBest = [ ]
while(coins[i]<=amount){
amount = amount - coins[i];
best.push(coins[i]);
}
if(amount>0 && coins.length>1){
tempBest = denomination(coins.slice(0,i).concat(coins.slice(i+1,coins.length)), amount);
//best = best.concat(denomination(coins.splice(i,1), amount));
}
if(tempBest.length!=0 || (best.length!=0 && amount==0)){
best = best.concat(tempBest);
if(original_best.length==0 ){
original_best = best
}else if(original_best.length > best.length ){
original_best = best;
}
}
}
return original_best;
}
denomination( [1,10,3,9] , 19 );
이것은 자바 스크립트 솔루션이며 재귀를 사용합니다.
스칼라 프로그래밍 언어에서는 다음과 같이합니다.
def countChange(money: Int, coins: List[Int]): Int = {
money match {
case 0 => 1
case x if x < 0 => 0
case x if x >= 1 && coins.isEmpty => 0
case _ => countChange(money, coins.tail) + countChange(money - coins.head, coins)
}
}
어, 지금 바보 같아 아래에는 지나치게 복잡한 솔루션 이 있습니다. 결국 솔루션 이므로 결국 보존하겠습니다 . 간단한 해결책은 다음과 같습니다.
// Generate a pretty string
val coinNames = List(("quarter", "quarters"),
("dime", "dimes"),
("nickel", "nickels"),
("penny", "pennies"))
def coinsString =
Function.tupled((quarters: Int, dimes: Int, nickels:Int, pennies: Int) => (
List(quarters, dimes, nickels, pennies)
zip coinNames // join with names
map (t => (if (t._1 != 1) (t._1, t._2._2) else (t._1, t._2._1))) // correct for number
map (t => t._1 + " " + t._2) // qty name
mkString " "
))
def allCombinations(amount: Int) =
(for{quarters <- 0 to (amount / 25)
dimes <- 0 to ((amount - 25*quarters) / 10)
nickels <- 0 to ((amount - 25*quarters - 10*dimes) / 5)
} yield (quarters, dimes, nickels, amount - 25*quarters - 10*dimes - 5*nickels)
) map coinsString mkString "\n"
다른 해결책은 다음과 같습니다. 이 솔루션은 각 코인이 다른 코인의 배수라는 관찰을 기반으로하여 코인으로 표시 할 수 있습니다.
// Just to make things a bit more readable, as these routines will access
// arrays a lot
val coinValues = List(25, 10, 5, 1)
val coinNames = List(("quarter", "quarters"),
("dime", "dimes"),
("nickel", "nickels"),
("penny", "pennies"))
val List(quarter, dime, nickel, penny) = coinValues.indices.toList
// Find the combination that uses the least amount of coins
def leastCoins(amount: Int): Array[Int] =
((List(amount) /: coinValues) {(list, coinValue) =>
val currentAmount = list.head
val numberOfCoins = currentAmount / coinValue
val remainingAmount = currentAmount % coinValue
remainingAmount :: numberOfCoins :: list.tail
}).tail.reverse.toArray
// Helper function. Adjust a certain amount of coins by
// adding or subtracting coins of each type; this could
// be made to receive a list of adjustments, but for so
// few types of coins, it's not worth it.
def adjust(base: Array[Int],
quarters: Int,
dimes: Int,
nickels: Int,
pennies: Int): Array[Int] =
Array(base(quarter) + quarters,
base(dime) + dimes,
base(nickel) + nickels,
base(penny) + pennies)
// We decrease the amount of quarters by one this way
def decreaseQuarter(base: Array[Int]): Array[Int] =
adjust(base, -1, +2, +1, 0)
// Dimes are decreased this way
def decreaseDime(base: Array[Int]): Array[Int] =
adjust(base, 0, -1, +2, 0)
// And here is how we decrease Nickels
def decreaseNickel(base: Array[Int]): Array[Int] =
adjust(base, 0, 0, -1, +5)
// This will help us find the proper decrease function
val decrease = Map(quarter -> decreaseQuarter _,
dime -> decreaseDime _,
nickel -> decreaseNickel _)
// Given a base amount of coins of each type, and the type of coin,
// we'll produce a list of coin amounts for each quantity of that particular
// coin type, up to the "base" amount
def coinSpan(base: Array[Int], whichCoin: Int) =
(List(base) /: (0 until base(whichCoin)).toList) { (list, _) =>
decrease(whichCoin)(list.head) :: list
}
// Generate a pretty string
def coinsString(base: Array[Int]) = (
base
zip coinNames // join with names
map (t => (if (t._1 != 1) (t._1, t._2._2) else (t._1, t._2._1))) // correct for number
map (t => t._1 + " " + t._2)
mkString " "
)
// So, get a base amount, compute a list for all quarters variations of that base,
// then, for each combination, compute all variations of dimes, and then repeat
// for all variations of nickels.
def allCombinations(amount: Int) = {
val base = leastCoins(amount)
val allQuarters = coinSpan(base, quarter)
val allDimes = allQuarters flatMap (base => coinSpan(base, dime))
val allNickels = allDimes flatMap (base => coinSpan(base, nickel))
allNickels map coinsString mkString "\n"
}
예를 들어 37 개의 동전의 경우 :
scala> println(allCombinations(37))
0 quarter 0 dimes 0 nickels 37 pennies
0 quarter 0 dimes 1 nickel 32 pennies
0 quarter 0 dimes 2 nickels 27 pennies
0 quarter 0 dimes 3 nickels 22 pennies
0 quarter 0 dimes 4 nickels 17 pennies
0 quarter 0 dimes 5 nickels 12 pennies
0 quarter 0 dimes 6 nickels 7 pennies
0 quarter 0 dimes 7 nickels 2 pennies
0 quarter 1 dime 0 nickels 27 pennies
0 quarter 1 dime 1 nickel 22 pennies
0 quarter 1 dime 2 nickels 17 pennies
0 quarter 1 dime 3 nickels 12 pennies
0 quarter 1 dime 4 nickels 7 pennies
0 quarter 1 dime 5 nickels 2 pennies
0 quarter 2 dimes 0 nickels 17 pennies
0 quarter 2 dimes 1 nickel 12 pennies
0 quarter 2 dimes 2 nickels 7 pennies
0 quarter 2 dimes 3 nickels 2 pennies
0 quarter 3 dimes 0 nickels 7 pennies
0 quarter 3 dimes 1 nickel 2 pennies
1 quarter 0 dimes 0 nickels 12 pennies
1 quarter 0 dimes 1 nickel 7 pennies
1 quarter 0 dimes 2 nickels 2 pennies
1 quarter 1 dime 0 nickels 2 pennies
이 블로그 항목은 XKCD 만화 의 인물에 대한이 배낭과 같은 문제를 해결합니다 . itemsdict과 exactcost값 을 간단히 변경하면 문제에 대한 모든 솔루션을 얻을 수 있습니다.
문제가 최소 비용을 사용하는 변경을 찾는 것이면, 최고 가치의 코인을 많이 사용하는 순진한 욕심 많은 알고리즘이 코인과 목표 금액의 일부 조합에서 실패 할 수 있습니다. 예를 들어 값이 1, 3 및 4 인 코인이있는 경우; 목표 금액이 6이면 탐욕 알고리즘은 값 3, 2 및 2를 사용할 수 있음을 쉽게 알 수있을 때 값 4, 1 및 1의 동전 3 개를 제안 할 수 있습니다.
- 아일랜드 사람.
public class Coins {
static int ac = 421;
static int bc = 311;
static int cc = 11;
static int target = 4000;
public static void main(String[] args) {
method2();
}
public static void method2(){
//running time n^2
int da = target/ac;
int db = target/bc;
for(int i=0;i<=da;i++){
for(int j=0;j<=db;j++){
int rem = target-(i*ac+j*bc);
if(rem < 0){
break;
}else{
if(rem%cc==0){
System.out.format("\n%d, %d, %d ---- %d + %d + %d = %d \n", i, j, rem/cc, i*ac, j*bc, (rem/cc)*cc, target);
}
}
}
}
}
}
O'reily의 "Python For Data Analysis"책에서이 깔끔한 코드를 발견했습니다. 그것은 게으른 구현과 int 비교를 사용하며 소수를 사용하여 다른 명칭으로 수정 될 수 있다고 가정합니다. 그것이 당신을 위해 어떻게 작동하는지 알려주세요!
def make_change(amount, coins=[1, 5, 10, 25], hand=None):
hand = [] if hand is None else hand
if amount == 0:
yield hand
for coin in coins:
# ensures we don't give too much change, and combinations are unique
if coin > amount or (len(hand) > 0 and hand[-1] < coin):
continue
for result in make_change(amount - coin, coins=coins,
hand=hand + [coin]):
yield result이것이 Zihan의 답변 개선입니다. 교단이 1 센트에 불과할 때 불필요한 루프가 많이 발생합니다.
직관적이고 비재 귀적입니다.
public static int Ways2PayNCents(int n)
{
int numberOfWays=0;
int cent, nickel, dime, quarter;
for (quarter = 0; quarter <= n/25; quarter++)
{
for (dime = 0; dime <= n/10; dime++)
{
for (nickel = 0; nickel <= n/5; nickel++)
{
cent = n - (quarter * 25 + dime * 10 + nickel * 5);
if (cent >= 0)
{
numberOfWays += 1;
Console.WriteLine("{0},{1},{2},{3}", quarter, dime, nickel, cent);
}
}
}
}
return numberOfWays;
}
간단한 자바 솔루션 :
public static void main(String[] args)
{
int[] denoms = {4,2,3,1};
int[] vals = new int[denoms.length];
int target = 6;
printCombinations(0, denoms, target, vals);
}
public static void printCombinations(int index, int[] denom,int target, int[] vals)
{
if(target==0)
{
System.out.println(Arrays.toString(vals));
return;
}
if(index == denom.length) return;
int currDenom = denom[index];
for(int i = 0; i*currDenom <= target;i++)
{
vals[index] = i;
printCombinations(index+1, denom, target - i*currDenom, vals);
vals[index] = 0;
}
}
이것은 청구서를 가져 와서 합계에 도달 할 때까지 더 작은 청구서를 재귀 적으로 취한 다음 동일한 명칭의 청구서를 가져 가서 다시 재귀하는 간단한 재귀 알고리즘입니다. 그림은 아래 샘플 출력을 참조하십시오.
var bills = new int[] { 100, 50, 20, 10, 5, 1 };
void PrintAllWaysToMakeChange(int sumSoFar, int minBill, string changeSoFar)
{
for (int i = minBill; i < bills.Length; i++)
{
var change = changeSoFar;
var sum = sumSoFar;
while (sum > 0)
{
if (!string.IsNullOrEmpty(change)) change += " + ";
change += bills[i];
sum -= bills[i];
if (sum > 0)
{
PrintAllWaysToMakeChange(sum, i + 1, change);
}
}
if (sum == 0)
{
Console.WriteLine(change);
}
}
}
PrintAllWaysToMakeChange(15, 0, "");
다음을 인쇄합니다.
10 + 5
10 + 1 + 1 + 1 + 1 + 1
5 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
5 + 5 + 1 + 1 + 1 + 1 + 1
5 + 5 + 5
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
/*
* make a list of all distinct sets of coins of from the set of coins to
* sum up to the given target amount.
* Here the input set of coins is assumed yo be {1, 2, 4}, this set MUST
* have the coins sorted in ascending order.
* Outline of the algorithm:
*
* Keep track of what the current coin is, say ccn; current number of coins
* in the partial solution, say k; current sum, say sum, obtained by adding
* ccn; sum sofar, say accsum:
* 1) Use ccn as long as it can be added without exceeding the target
* a) if current sum equals target, add cc to solution coin set, increase
* coin coin in the solution by 1, and print it and return
* b) if current sum exceeds target, ccn can't be in the solution, so
* return
* c) if neither of the above, add current coin to partial solution,
* increase k by 1 (number of coins in partial solution), and recuse
* 2) When current denomination can no longer be used, start using the
* next higher denomination coins, just like in (1)
* 3) When all denominations have been used, we are done
*/
#include <iostream>
#include <cstdlib>
using namespace std;
// int num_calls = 0;
// int num_ways = 0;
void print(const int coins[], int n);
void combine_coins(
const int denoms[], // coins sorted in ascending order
int n, // number of denominations
int target, // target sum
int accsum, // accumulated sum
int coins[], // solution set, MUST equal
// target / lowest denom coin
int k // number of coins in coins[]
)
{
int ccn; // current coin
int sum; // current sum
// ++num_calls;
for (int i = 0; i < n; ++i) {
/*
* skip coins of lesser denomination: This is to be efficient
* and also avoid generating duplicate sequences. What we need
* is combinations and without this check we will generate
* permutations.
*/
if (k > 0 && denoms[i] < coins[k - 1])
continue; // skip coins of lesser denomination
ccn = denoms[i];
if ((sum = accsum + ccn) > target)
return; // no point trying higher denominations now
if (sum == target) {
// found yet another solution
coins[k] = ccn;
print(coins, k + 1);
// ++num_ways;
return;
}
coins[k] = ccn;
combine_coins(denoms, n, target, sum, coins, k + 1);
}
}
void print(const int coins[], int n)
{
int s = 0;
for (int i = 0; i < n; ++i) {
cout << coins[i] << " ";
s += coins[i];
}
cout << "\t = \t" << s << "\n";
}
int main(int argc, const char *argv[])
{
int denoms[] = {1, 2, 4};
int dsize = sizeof(denoms) / sizeof(denoms[0]);
int target;
if (argv[1])
target = atoi(argv[1]);
else
target = 8;
int *coins = new int[target];
combine_coins(denoms, dsize, target, 0, coins, 0);
// cout << "num calls = " << num_calls << ", num ways = " << num_ways << "\n";
return 0;
}
C # 함수는 다음과 같습니다.
public static void change(int money, List<int> coins, List<int> combination)
{
if(money < 0 || coins.Count == 0) return;
if (money == 0)
{
Console.WriteLine((String.Join("; ", combination)));
return;
}
List<int> copy = new List<int>(coins);
copy.RemoveAt(0);
change(money, copy, combination);
combination = new List<int>(combination) { coins[0] };
change(money - coins[0], coins, new List<int>(combination));
}
다음과 같이 사용하십시오.
change(100, new List<int>() {5, 10, 25}, new List<int>());
다음을 인쇄합니다.
25; 25; 25; 25
10; 10; 10; 10; 10; 25; 25
10; 10; 10; 10; 10; 10; 10; 10; 10; 10
5; 10; 10; 25; 25; 25
5; 10; 10; 10; 10; 10; 10; 10; 25
5; 5; 10; 10; 10; 10; 25; 25
5; 5; 10; 10; 10; 10; 10; 10; 10; 10; 10
5; 5; 5; 10; 25; 25; 25
5; 5; 5; 10; 10; 10; 10; 10; 10; 25
5; 5; 5; 5; 10; 10; 10; 25; 25
5; 5; 5; 5; 10; 10; 10; 10; 10; 10; 10; 10
5; 5; 5; 5; 5; 25; 25; 25
5; 5; 5; 5; 5; 10; 10; 10; 10; 10; 25
5; 5; 5; 5; 5; 5; 10; 10; 25; 25
5; 5; 5; 5; 5; 5; 10; 10; 10; 10; 10; 10; 10
5; 5; 5; 5; 5; 5; 5; 10; 10; 10; 10; 25
5; 5; 5; 5; 5; 5; 5; 5; 10; 25; 25
5; 5; 5; 5; 5; 5; 5; 5; 10; 10; 10; 10; 10; 10
5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 10; 10; 25
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 25; 25
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 10; 10; 10; 10
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 10; 25
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 10; 10; 10
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 25
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 10; 10
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 25
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 10
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5
자바 솔루션
import java.util.Arrays;
import java.util.Scanner;
public class nCents {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int cents=input.nextInt();
int num_ways [][] =new int [5][cents+1];
//putting in zeroes to offset
int getCents[]={0 , 0 , 5 , 10 , 25};
Arrays.fill(num_ways[0], 0);
Arrays.fill(num_ways[1], 1);
int current_cent=0;
for(int i=2;i<num_ways.length;i++){
current_cent=getCents[i];
for(int j=1;j<num_ways[0].length;j++){
if(j-current_cent>=0){
if(j-current_cent==0){
num_ways[i][j]=num_ways[i-1][j]+1;
}else{
num_ways[i][j]=num_ways[i][j-current_cent]+num_ways[i-1][j];
}
}else{
num_ways[i][j]=num_ways[i-1][j];
}
}
}
System.out.println(num_ways[num_ways.length-1][num_ways[0].length-1]);
}
}
다른 조합도 인쇄하는 아래 Java 솔루션입니다. 이해하기 쉬운. 아이디어는
합계 5
해결책은
5 - 5(i) times 1 = 0
if(sum = 0)
print i times 1
5 - 4(i) times 1 = 1
5 - 3 times 1 = 2
2 - 1(j) times 2 = 0
if(sum = 0)
print i times 1 and j times 2
and so on......
각 루프의 나머지 합이 교파보다 작 으면, 즉 나머지 합계 1이 2보다 작 으면 루프를 끊으십시오.
아래의 전체 코드
실수가있을 경우 수정 해주세요
public class CoinCombinbationSimple {
public static void main(String[] args) {
int sum = 100000;
printCombination(sum);
}
static void printCombination(int sum) {
for (int i = sum; i >= 0; i--) {
int sumCopy1 = sum - i * 1;
if (sumCopy1 == 0) {
System.out.println(i + " 1 coins");
}
for (int j = sumCopy1 / 2; j >= 0; j--) {
int sumCopy2 = sumCopy1;
if (sumCopy2 < 2) {
break;
}
sumCopy2 = sumCopy1 - 2 * j;
if (sumCopy2 == 0) {
System.out.println(i + " 1 coins " + j + " 2 coins ");
}
for (int k = sumCopy2 / 5; k >= 0; k--) {
int sumCopy3 = sumCopy2;
if (sumCopy2 < 5) {
break;
}
sumCopy3 = sumCopy2 - 5 * k;
if (sumCopy3 == 0) {
System.out.println(i + " 1 coins " + j + " 2 coins "
+ k + " 5 coins");
}
}
}
}
}
}
다음은 재귀와 메모를 사용하여 O (mxn)의 복잡성을 초래하는 파이썬 기반 솔루션입니다.
def get_combinations_dynamic(self, amount, coins, memo): end_index = len(coins) - 1 memo_key = str(amount)+'->'+str(coins) if memo_key in memo: return memo[memo_key] remaining_amount = amount if amount < 0: return [] if amount == 0: return [[]] combinations = [] if len(coins) <= 1: if amount % coins[0] == 0: combination = [] for i in range(amount // coins[0]): combination.append(coins[0]) list.sort(combination) if combination not in combinations: combinations.append(combination) else: k = 0 while remaining_amount >= 0: sub_combinations = self.get_combinations_dynamic(remaining_amount, coins[:end_index], memo) for combination in sub_combinations: temp = combination[:] for i in range(k): temp.append(coins[end_index]) list.sort(temp) if temp not in combinations: combinations.append(temp) k += 1 remaining_amount -= coins[end_index] memo[memo_key] = combinations return combinations
아래는 파이썬 솔루션입니다.
x = []
dic = {}
def f(n,r):
[a,b,c,d] = r
if not dic.has_key((n,a,b,c,d)): dic[(n,a,b,c,d)] = 1
if n>=25:
if not dic.has_key((n-25,a+1,b,c,d)):f(n-25,[a+1,b,c,d])
if not dic.has_key((n-10,a,b+1,c,d)):f(n-10,[a,b+1,c,d])
if not dic.has_key((n-5,a,b,c+1,d)):f(n-5,[a,b,c+1,d])
if not dic.has_key((n-1,a,b,c,d+1)):f(n-1,[a,b,c,d+1])
elif n>=10:
if not dic.has_key((n-10,a,b+1,c,d)):f(n-10,[a,b+1,c,d])
if not dic.has_key((n-5,a,b,c+1,d)):f(n-5,[a,b,c+1,d])
if not dic.has_key((n-1,a,b,c,d+1)):f(n-1,[a,b,c,d+1])
elif n>=5:
if not dic.has_key((n-5,a,b,c+1,d)):f(n-5,[a,b,c+1,d])
if not dic.has_key((n-1,a,b,c,d+1)):f(n-1,[a,b,c,d+1])
elif n>=1:
if not dic.has_key((n-1,a,b,c,d+1)):f(n-1,[a,b,c,d+1])
else:
if r not in x:
x.extend([r])
f(100, [0,0,0,0])
print x
반응형
'Programming' 카테고리의 다른 글
| 어플리케이션 서버와 서블릿 컨테이너의 차이점은 무엇입니까? (0) | 2020.08.03 |
|---|---|
| 부트 스트랩 3-행 클래스가 컨테이너보다 넓은 이유는 무엇입니까? (0) | 2020.08.03 |
| Go와 비교하여 왜 느린가 (Java와 비교)? (0) | 2020.08.03 |
| Google Maps API V3-정확히 같은 지점에 여러 마커 (0) | 2020.08.03 |
| Python 스크립트를 실행하려고 할 때“ImportError : No module named” (0) | 2020.08.03 |