总和为S的最小硬币数量

Question

给定 N 个硬币的列表，它们的值 (V1, V2, ... , VN) 以及总和 S。找到总和为 S 的硬币的最小数量（我们可以使用一种类型的硬币数量为我们想要），或者报告不可能以总和为 S 的方式选择硬币。

我试图理解动态规划，但还没有弄清楚。我不明白给定的解释，所以也许你可以给我一些如何编写这个任务的提示？没有代码，只是我应该从哪里开始的想法。

谢谢。

Answer 1

这个问题的准确答案在这里得到了很好的解释。
http://www.topcoder.com/tc?module=Static& ;d1=教程&d2=dynProg

Answer 2

这是一个经典的背包问题，请查看此处以获取更多信息：维基百科背包问题

您还应该查看一些排序，特别是从最大到最小的值排序。

Answer 3

正如已经指出的，动态规划最适合解决这个问题。我为此编写了一个Python程序：-

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)

对于输入：

12
2 3 5

输出为：

[0, -1, 1, 1, 2, 1, 2, 2, 2, 3, 2, 3, 3]
3

list_index 是所需的总数，list_index 的值是编号。获得该总数所需的硬币。上述输入（得到值 12）的答案是 3（值 5、5、2 的硬币）。

Answer 4

我认为你想要的方法是这样的：

你知道你想要产生一个总和S。生产S的唯一方法是首先生产S-V1，然后添加价值V1的硬币；或生产S-V2，然后添加有价值V2的硬币；或者...

，T=S-V1 可以从 T-V1 或 T-V2 生成，或者...

反过来 以这种方式退后一步，您可以确定从 V 生成 S 的最佳方法（如果有）。

Answer 5

问题已经得到解答，但我想提供我编写的工作 C 代码，如果它对任何人有帮助的话。 在此处输入代码

代码具有硬编码输入，但这只是为了保持简单。最终的解决方案是数组 min ，其中包含每个总和所需的硬币数量。

#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 6

我不知道动态规划，但这就是我要做的。从零开始，逐步达到 S。用一枚硬币生产一套，然后用该套生产两枚硬币，依此类推...搜索 S，并忽略所有大于 S 的值。对于每个值，请记住所使用的硬币数量。

Answer 7

很多人已经回答了这个问题。这是使用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 8

主要思想是 - 对于每个硬币 j，value[j] <= i（即总和），我们查看为 i-value[j]（比方说 m）总和（之前找到的）找到的最小硬币数量。如果 m+1 小于当前总和 i​​ 已找到的最小硬币数量，则我们更新数组中的硬币数量。

对于前 - sum = 11 n=3 且 value[] = {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 

正如我们可以观察到的 sum 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.  

因此，对于 sum=11，我们将得到答案 3(5+5+1) 。

这是 C 中的代码。它类似于 topcoder 页面中给出的伪代码，其参考在上面的答案之一中提供。

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

我知道这是一个老问题，但这是 Java 中的解决方案。

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);
    }
}

Answer 11

对于快速递归解决方案，您可以检查此链接：java解决方案

我正在执行找到完美硬币组合所需的最少步骤。
假设我们有 coins = [20, 15, 7] 和 monetaryValue = 37。我的解决方案将按如下方式工作：

[20] -> sum of array bigger than 37? NO -> add it to itself
[20, 20] greater than 37? YES (20 + 20) -> remove last and jump to smaller coin
[20, 15] 35 OK
[20, 15, 15] 50 NO
[20, 15, 7] 42 NO
// Replace biggest number and repeat
[15] 15 OK
[15, 15] 30 OK
[15, 15, 15] 45 NO
[15, 15, 7] 37! RETURN NUMBER!

Answer 12

def leastCoins(lst, x):
temp = []
if x == 0:
    return 0
else:       
    while x != 0:
        if len(lst) == 0:
            return "Not Possible"
        if x % max(lst) == 0:
            temp.append((max(lst), x//max(lst)))
            x = 0
        elif max(lst) < x:
            temp.append((max(lst), x//max(lst)))
            x = x % max(lst)
            lst.remove(max(lst))
        else:
            lst.remove(max(lst))
return dict(temp) 

最少硬币([17,18,2], 100652895656565)