합계가 최소 인 동전의 수 S

Question

N 개의 동전의 목록, 그 값 (V1, V2, ..., VN) 및 총합 S가 주어지면 최소 동전의 수를 찾습니다. S (우리가 원했던 한 종류의 많은 동전을 사용할 수 있음) 또는 S까지 합계하는 방식으로 동전을 선택할 수 없다고보고합니다.

나는 동적 프로그래밍, 헤븐 그걸 알아 냈어. 나는 주어진 설명을 이해하지 못하기 때문에이 작업을 프로그래밍하는 방법에 대한 몇 가지 힌트를 던져 줄 수 있을까요? 코드가 없으며 시작해야하는 아이디어입니다.

감사합니다.

Answer 1

이 고전 배낭 문제, 좀 더 많은 정보는 여기를보십시오 : Wikipedia Knapsack Problem

또한 특별히 큰에서 가장 작은 값으로 정렬, 일부 정렬 봐야한다.

Answer 2

나는 당신이 원하는 방법은 다음과 같이 생각 :

당신은 합 S을 생산하려는 것을 알고있다. S을 생산하는 유일한 방법은 먼저 S-V1을 생산 한 다음 값이 V1 인 동전을 추가하는 것입니다. 또는 S-V2을 생성 한 다음 값이 V2 인 동전을 추가하십시오. 에서 S을 생산하는 (있는 경우) 또는 ...

가 차례로, T=S-V1이 ...

을 이런 식으로 다시 스테핑으로 T-V1, 또는 T-V2, 또는에서 생산 될 것입니다, 당신은 최선의 방법을 결정할 수 있습니다 V s.

Answer 3

동적 프로그래밍에 대해서는 잘 모릅니다. 그러나 이것이 내가하는 방법입니다. 0에서 시작하여 S으로 이동하십시오. 하나의 동전으로 세트를 만든 다음 그 세트로 두 개의 동전 세트를 생산하는 식으로 S을 검색하고 S보다 큰 모든 값을 무시하십시오. 각 값에 대해 사용 된 동전의 수를 기억하십시오.

Answer 4

이 문제에 대한 정확한 대답은 여기에서 자세히 설명합니다. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg

Answer 5

많은 사람들이 이미 질문에 답변했습니다. 여기에 DP를 사용하는 코드가 있습니다

public static List<Integer> getCoinSet(int S, int[] coins) { 
    List<Integer> coinsSet = new LinkedList<Integer>(); 
    if (S <= 0) return coinsSet; 

    int[] coinSumArr = buildCoinstArr(S, coins); 

    if (coinSumArr[S] < 0) throw new RuntimeException("Not possible to get given sum: " + S); 

    int i = S; 
    while (i > 0) { 
     int coin = coins[coinSumArr[i]]; 
     coinsSet.add(coin); 
     i -= coin; 
    } 

    return coinsSet; 
} 

public static int[] buildCoinstArr(int S, int[] coins) { 
    Arrays.sort(coins); 
    int[] result = new int[S + 1]; 

    for (int s = 1; s <= S; s++) { 
     result[s] = -1; 
     for (int i = coins.length - 1; i >= 0; i--) { 
      int coin = coins[i]; 
      if (coin <= s && result[s - coin] >= 0) { 
       result[s] = i; 
       break; 
      } 
     } 
    } 

    return result; 
} 

Answer 6

이미 지적했듯이 동적 프로그래밍은이 문제에 가장 적합합니다. 나는 이것에 대한 파이썬 프로그램을 작성했습니다 : - :

12 2 3 5

이 출력은 다음과 같습니다 입력하여

def sumtototal(total, coins_list): 
    s = [0] 
    for i in range(1, total+1): 
     s.append(-1) 
     for coin_val in coins_list: 
      if i-coin_val >=0 and s[i-coin_val] != -1 and (s[i] > s[i-coin_val] or s[i] == -1): 
       s[i] = 1 + s[i-coin_val] 

    print s 
    return s[total] 

total = input() 
coins_list = map(int, raw_input().split(' ')) 
print sumtototal(total, coins_list) 

[0, -1, 1, 1, 2, 1, 2, 2, 2, 3, 2, 3, 3] 3 list_index 필요한 총과 가치입니다 list_index는 no입니다. 그 총계를 얻기 위하여 필요로 한 동전의. 위의 입력 (값 12 가져 오기)에 대한 대답은 3 (값 5, 5, 2의 동전)입니다.

Answer 7

질문에 이미 답변되어 있지만 누군가에게 도움이된다면 필자가 작성한 작업 C 코드를 제공하고 싶습니다.enter code here

코드에는 하드 코딩 된 입력이 있지만 단순하게 유지하는 것입니다. 최종 솔루션은 각 합계에 필요한 동전 수를 포함하는 배열 분입니다.

#include"stdio.h" 
#include<string.h> 

int min[12] = {100}; 
int coin[3] = {1, 3, 5}; 

void 
findMin (int sum) 
{ 
    int i = 0; int j=0; 
    min [0] = 0; 

    for (i = 1; i <= sum; i++) { 
     /* Find solution for Sum = 0..Sum = Sum -1, Sum, i represents sum 
     * at each stage */ 
     for (j=0; j<= 2; j++) { 
      /* Go over each coin that is lesser than the sum at this stage 
      * i.e. sum = i */ 
      if (coin[j] <= i) { 
       if ((1 + min[(i - coin[j])]) <= min[i]) { 
        /* E.g. if coin has value 2, then for sum i = 5, we are 
        * looking at min[3] */ 
        min[i] = 1 + min[(i-coin[j])]; 
        printf("\nsetting min[%d] %d",i, min[i]); 
       } 
      } 
     } 
    } 
} 
void 
initializeMin() 
{ 
    int i =0; 
    for (i=0; i< 12; i++) { 
     min[i] = 100; 
    } 
} 
void 
dumpMin() 
{ 
    int i =0; 
    for (i=0; i< 12; i++) { 
     printf("\n Min[%d]: %d", i, min[i]); 
    } 
} 
int main() 
{ 
    initializeMin(); 
    findMin(11); 
    dumpMin(); 
} 

Answer 8

주요 아이디어는 - 각 동전 J를 들어, 값 [J] < = I (즉, 합) 우리는 I-값 [J]에 대한 발견 동전의 최소 수를 보면이 합 (m 가정 해 봅시다) (이전에 발견됨). m + 1이 현재 합계 i에 대해 이미 발견 된 최소 동전 수보다 작 으면 배열의 동전 수를 업데이트합니다. 예를 들어

- 후 합계 = 11, N = 3 값 [] = {1,3,5}
우리가

i- 1 mins[i] - 1 
i- 2 mins[i] - 2 
i- 3 mins[i] - 3 
i- 3 mins[i] - 1 
i- 4 mins[i] - 2 
i- 5 mins[i] - 3 
i- 5 mins[i] - 1 
i- 6 mins[i] - 2 
i- 7 mins[i] - 3 
i- 8 mins[i] - 4 
i- 8 mins[i] - 2 
i- 9 mins[i] - 3 
i- 10 mins[i] - 4 
i- 10 mins[i] - 2 
i- 11 mins[i] - 3 

우리 합 I = 3 관찰 할 수있는 바와 같이

얻기 출력 5, 8, 10, 우리는 다음과 같은 방법으로 이전 최소에서시 개선 -

가

sum = 3, 3 (1+1+1) coins of 1 to one 3 value coin 
sum = 5, 3 (3+1+1) coins to one 5 value coin 
sum = 8, 4 (5+1+1+1) coins to 2 (5+3) coins 
sum = 10, 4 (5+3+1+1) coins to 2 (5+5) coins. 

그래서 합계 = 11 우리는 3 (5 + 5 + 1)로 답을 얻을 것이다.

여기에 C 코드가 있습니다. topcoder 페이지에있는 pseudocode와 유사합니다. 위의 답변 중 하나에서 참조가 제공됩니다.

int findDPMinCoins(int value[], int num, int sum) 
{ 
    int mins[sum+1]; 
    int i,j; 

    for(i=1;i<=sum;i++) 
     mins[i] = INT_MAX; 

    mins[0] = 0; 
    for(i=1;i<=sum;i++) 
    { 
     for(j=0;j<num;j++) 
     { 
      if(value[j]<=i && ((mins[i-value[j]]+1) < mins[i])) 
      { 
       mins[i] = mins[i-value[j]] + 1; 
       printf("i- %d mins[i] - %d\n",i,mins[i]); 
      } 
     } 
    } 
    return mins[sum]; 
} 

Answer 9

int getMinCoins(int arr[],int sum,int index){ 

     int INFINITY=1000000; 
     if(sum==0) return 0; 
     else if(sum!=0 && index<0) return INFINITY; 

     if(arr[index]>sum) return getMinCoins(arr, sum, index-1); 

     return Math.min(getMinCoins(arr, sum, index-1), getMinCoins(arr, sum-arr[index], index-1)+1); 
    } 

는 i 번째 동전을 고려하십시오. 그것은 포함되거나 포함되지 않을 것입니다. 그것이 포함되면, 가치 합계는 동전 값에 의해 감소하고 사용 된 동전의 수는 1 씩 증가합니다. 포함되지 않으면 남은 동전을 비슷하게 탐험해야합니다. 우리는 최소한 두 가지 사례를 취합니다.

Answer 10

나는 이것이 오래된 질문이라는 것을 알고 있었지만 이것은 자바의 해결책이다.

import java.util.Arrays; 
import java.util.HashMap; 
import java.util.Map; 

public class MinCoinChange { 

    public static void min(int[] coins, int money) { 
     int[] dp = new int[money + 1]; 
     int[] parents = new int[money + 1]; 
     int[] usedCoin = new int[money + 1]; 
     Arrays.sort(coins); 
     Arrays.fill(dp, Integer.MAX_VALUE); 
     Arrays.fill(parents, -1); 

     dp[0] = 0; 
     for (int i = 1; i <= money; ++i) { 
      for (int j = 0; j < coins.length && i >= coins[j]; ++j) { 
       if (dp[i - coins[j]] + 1 < dp[i]) { 
        dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1); 
        parents[i] = i - coins[j]; 
        usedCoin[i] = coins[j]; 
       } 
      } 
     } 
     int parent = money; 
     Map<Integer, Integer> result = new HashMap<>(); 
     while (parent != 0) { 
      result.put(usedCoin[parent], result.getOrDefault(usedCoin[parent], 0) + 1); 
      parent = parents[parent]; 
     } 
     System.out.println(result); 
    } 

    public static void main(String[] args) { 
     int[] coins = { 1, 5, 10, 25 }; 
     min(coins, 30); 
    } 
}