给定N枚硬币的价值(V1,V2,...,VN)和总和S，找到使得它们的和为S的最小数量的硬币(我们可以使用任意数量的同一种硬币)，或者报告无法选择硬币以便它们的和是S。
我试图理解动态规划，但还没想通。我不理解给出的解释，所以也许你能给我一些提示如何编程这个任务？不需要代码，只要点拨我该从哪里开始。
谢谢。
我试图理解动态规划，但还没想通。我不理解给出的解释，所以也许你能给我一些提示如何编程这个任务？不需要代码，只要点拨我该从哪里开始。
谢谢。
12个回答
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 上的值是获得该总数所需的硬币数量。以上输入的答案是 3（使用面值为 5、5、2 的硬币）。
- Barun Sharma
2
我认为你想要的方法是这样的：
你知道你想要产生一个总和S。产生S的唯一方法是先产生S-V1，然后再添加价值为V1的硬币；或者先产生S-V2，然后再添加价值为V2的硬币；或者......
依次类推，T=S-V1可以从T-V1或T-V2等方式得到。
通过这种方式，你可以确定从你的V中产生S的最佳方法，如果有的话。
你知道你想要产生一个总和S。产生S的唯一方法是先产生S-V1，然后再添加价值为V1的硬币；或者先产生S-V2，然后再添加价值为V2的硬币；或者......
依次类推，T=S-V1可以从T-V1或T-V2等方式得到。
通过这种方式，你可以确定从你的V中产生S的最佳方法，如果有的话。
- Chowlett
2
1这种技术被称为令人困惑的通用术语“动态规划”。 - Phrogz
更具体地说，当在自顶向下的方式中使用记忆化时。 - joscarsson
1
问题已经得到回答，但我想提供我编写的可行的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();
}
- SeattleOrBayArea
0
我知道这是一个老问题，但这是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);
}
}
- Bahador Biglari
0
我不知道动态规划，但这是我会做的方式。从零开始，一步步到达S。先生成一个硬币集合，然后用该集合生成一个两个硬币的集合，以此类推...搜索S，忽略所有大于S的值。对于每个值，记住使用的硬币数量。
- Dialecticus
0
主要思想是 - 对于每个硬币j，value[j] <= i（即sum），我们查找i-value[j]（假设为m）的最小硬币数量（之前找到的）。如果m + 1小于当前总和i已经找到的最小硬币数，则更新数组中的硬币数。
例如 - sum = 11 n = 3，value [] = {1,3,5}
以下是我们得到的输出
例如 - 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
从我们观察到的 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];
}
- learner
0
为了快速递归解决方案，您可以查看此链接：java solution
我正在研究寻找完美硬币组合所需的最小步骤。
假设我们有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!
- Lucio
0
很多人已经回答了这个问题。这里是一个使用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;
}
- Sergey
3
我猜返回的链表是用来组成所需总和的硬币列表，我的猜测对吗？如果是这样，在集合{8, 7, 1}和总和14的情况下，这个程序似乎无法正常工作（我得到了一个8和六个1）。如果不是，请问列表中的数字“coinsSet”代表什么？ - JohnK
问题定义允许重复使用硬币（“我们可以使用任意数量的同一类型硬币”）。该列表表示加起来等于给定总和的硬币。在您的示例中{8, 7, 1} -> Sum({8, 1, 1, 1 ,1 , 1, 1}) = 14。 - Sergey
Sergey，对于集合{8, 7, 1}和总和14的问题，正确答案是使用2枚面值为7的硬币（7+7 = 14）。你使用7枚硬币的答案8+1+1+1+1+1+1 = 14是错误的。 - P L Patodia
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接