最小硬币变化打印所有组合
给定一组硬币面额硬币和一个总数，找出所有可能的组合，使硬币总数达到最小。在我的解决方案中，我在表[I]中记录了总计为I的最小硬币数。我不确定这将如何修改以存储总计为I的实际硬币，并确保在这种情况下包括这两种可能性。我看过其他关于堆栈溢出的代码，但我只找到可以打印任何一个最佳解决方案的代码。
输入：最小硬币（10，[2,3,5,6,7,8]）
输出：[[5,5]，[2,8]]
INT_MAX = 2 ** 63 - 1
def minimum_coins(total, coins)
table = Array.new(total + 1)
table[0] = 0
(1..total).to_a.each do |i|
table[i] = INT_MAX
end
(1..total).to_a.each do |i|
(0..coins.length-1).to_a.each do |j|
if coins[j] <= i
sub_res = table[i-coins[j]]
if sub_res != INT_MAX && sub_res + 1 < table[i]
table[i] = sub_res + 1
end
end
end
end
puts table.inspect
end
minimum_coins(10, [2,3,5,6,7,8])
共有3个答案
我做了一个迭代程序，可以计算得到给定数量的美分所需的最低硬币数量（美元）。它是迭代的，但希望它能有所帮助！
import java.util.*;
public class CoinProblem
{
public static void main(String[] args)
{
System.out.println("----------------------------COIN PROBLEM--------------------------");
System.out.println("Denominations: \nCent - 1\nNickel - 5\nDime - 10\nQuarter - 25");
Map<Integer, Integer> map = new HashMap<Integer, Integer> ();
System.out.println("\nENTER TARGET NUMBER (CENTS): ");
Scanner sc = new Scanner(System.in);
int target = Integer.parseInt(sc.next());
int count = numCoins(target, map);
System.out.println("\nMINIMUM NUMBER OF COINS REQUIRED: " + count);
System.out.println( map.get(1) + " CENTS");
System.out.println( map.get(5) + " NICKELS");
System.out.println( map.get(10) + " DIMES");
System.out.println( map.get(25) + " QUARTERS");
System.out.println("------------------------------------------------------------------");
}
public static int numCoins(int target, Map<Integer, Integer> map)
{
int cent = 1;
int nickel = 5;
int dime = 10;
int quarter = 25;
map.put(cent, 0);
map.put(nickel, 0);
map.put(dime, 0);
map.put(quarter, 0);
int count = 0;
if (target >= 25)
{
if (target % 25 == 0)
{
count += target/25;
map.put(quarter, count);
return count;
}
else
{
count += target/25;
map.put(quarter, count);
int remtarget = target%25;
if (remtarget >= 10)
{
if (remtarget % 10 == 0)
{
count += remtarget/10;
map.put(dime, remtarget/10);
return count;
}
else
{
count += remtarget/10;
map.put(dime, remtarget/10);
int fivetarget = remtarget%10;
if (fivetarget >= 5)
{
if (fivetarget % 5 == 0)
{
count += fivetarget/5;
map.put(nickel, fivetarget/5);
}
else
{
count += fivetarget/5;
map.put(nickel, fivetarget/5);
int ones = fivetarget%5;
count+= ones;
map.put(cent, ones);
}
}
else
{
count += fivetarget;
map.put(cent, fivetarget);
return count;
}
}
}
else
{
if (remtarget >= 5)
{
if (remtarget % 5 == 0)
{
count += remtarget/5;
map.put(nickel, remtarget/5);
}
else
{
count += remtarget/5;
map.put(nickel, remtarget/5);
int ones = remtarget%5;
count+= ones;
map.put(cent, ones);
}
}
else
{
count += remtarget;
map.put(cent, remtarget);
return count;
}
}
}
}
else
{
if (target == 0)
{
return 0;
}
if (target >= 10)
{
if (target % 10 == 0)
{
count += target/10;
map.put(dime, target/10);
return count;
}
else
{
count += target/10;
map.put(dime, target/10);
int ftarget = target%10;
if (ftarget >= 5)
{
if (ftarget % 5 == 0)
{
count += ftarget/5;
map.put(nickel, ftarget/5);
}
else
{
count += ftarget/5;
map.put(nickel, ftarget/5);
int otarget = ftarget%5;
count+= otarget;
map.put(cent, otarget);
}
}
else
{
count += ftarget;
map.put(cent, ftarget);
return count;
}
}
}
else
{
if (target > 5)
{
if (target % 5 == 0)
{
count += target/5;
map.put(nickel, target/5);
}
else
{
count += target/5;
map.put(nickel, target/5);
int o = target%5;
count+= o;
map.put(cent, o);
}
}
else
{
count += target;
map.put(cent, target);
return count;
}
}
}
return count;
}
}
让我们看看表条目包含成对的（BestCount，LastCoinList）。
如果sub_res 1
如果sub_res1=table[i]。BestCount然后只需添加硬币[j]值到LastCoinList
因此，最后，表[10]将包含BestValue=2和lastconlist=（5,7,8）
现在递归地从表[10]项展开到表[10-5]，到表[10-7]，再到表[10-8]，分别包含5,3和2，然后所有递归分支都在第0个项处停止。
让我们：
d[i] = minimum changes for i
所以如果d[i]==d[i-c]1，我们可以说，如果我们用硬币c进行交换，我们仍然可以得到i的最小硬币兑换。
代码：
def find(n, result, d, coins, changes, index):
if n == 0:
changes.append(result)
return
for i in range(index, len(coins)):
if n - coins[i] >= 0 and d[n] == d[n - coins[i]] + 1:
find(n - coins[i], result + [coins[i]], d, coins, changes, i)
def all_coin_changes(n, coins):
d = [n + 1] * (n + 1)
d[0] = 0
for i in range(1, n + 1):
for c in coins:
if i - c >= 0:
d[i] = min(d[i], d[i - c] + 1)
changes = []
find(n, [], d, coins, changes, 0)
return changes
print all_coin_changes(10, [2, 3, 5, 6, 7, 8])
# [[2, 8], [3, 7], [5, 5]]
print all_coin_changes(100, [2, 3, 5, 6, 7, 8])
# [[5, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8], [6, 6, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8], [6, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8], [7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8]]
如果你还有疑问，请不要犹豫，在这里留言评论。
-
例如：如果我有硬币：[6,11]，我需要最小的硬币来获得13，那么答案应该是2（11,6），这些是最小的硬币数量。 现在我需要打印组成这个答案的实际硬币。 这是输出： 总计： 1- 现在，公式应该是：循环到：Max（total）-容量（total），直到结果小于或等于零。 面额为：每个单位的容量（总数）
-
下面是最小硬币兑换问题的强力解决方案。它需要一个整数A（这是需要进行的更改）和一组硬币面额。它返回一个对象results，该对象具有基于硬币面额数组和硬币数组可以返回的最小硬币数。 例如，如果要求以的值为美分提供零钱，则它应返回分钟硬币和两个一角硬币的数组。 它返回正确的最小值，但不是正确的硬币数组。
-
具体而言，问题是： 给定面额数组<代码>硬币[]，每个硬币的限制数组<代码>限制[]和数量<代码>金额，返回所需的最小硬币数量，以获取<代码>金额，或者如果不可能，返回空值。另外，用溶液中使用的每个硬币的数量填充数组 这是我的解决方案： 但它一般不起作用。 我的问题是，例如，在这种情况下： 最佳解决方案是： 并且我的算法给出作为结果。换句话说，它失败了，每当在某种情况下，我将不得不使用比可能的更少
-
这是Leetcode的硬币兑换问题，在这里，给定面额的硬币是无限的，你必须找到满足给定金额所需的最小硬币。我尝试使用自顶向下的1D缓存阵列解决这个问题。基本测试用例通过了，但对于一些较大的总和和面额值，它失败了。我的假设是，我在遍历数组时做错了什么，可能遗漏了一些子问题的计算，但无法找到解决问题的方法。 问题陈述： 我的解决方案：
-
给定一个值N，如果我们想改变为N美分，并且我们有无限量的S={S1，S2，...，Sm}值的硬币，我们有多少种方法可以改变？硬币的顺序并不重要。不过还有一个额外的限制：你只能用正好是K的硬币换零钱。 例如，对于N=4，k=2和S={1,2,3}，有两个解：{2,2}，{1,3}。所以输出应该是2。 解决方案： 以上是递归解决方案。但是，我需要有关动态规划解决方案的帮助： 让表示与元素和硬币的总和。
-
我见过很多硬币更换问题，这个问题很独特。我尝试使用DP和递归，但我无法解决它。 这就是问题所在： 假设给定一个价格，X，其中X是美分，我有5种有限面额的硬币，1,5,10,20,50。我有不同数量的1、5、10、20、50分硬币。我想用最大数量的硬币来确定价格X。我该怎么做？（假设X总是可以用手头的硬币制作） 例如，如果价格X=52，并且 我有三枚一分硬币 我有四枚五分硬币 我有8枚10美分的硬币