动态规划硬币的改变决定
https://stackoverflow.com/questions/2633848
-
26-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我查看了一些旧的笔记我的算法的过程和动态的规划问题的看似棘手给我。我有一个问题，我们有无限供应的硬币，一些教派x1,x2,...x和我们想要做的改变对于一些值X。我们正在努力设计一个动态程序，以决定是否改变对X可以提出或没有(没有减少的硬币数量，或者返回其硬币，只要真正的或假)。
我已经做了一些思考这个问题，我可以看到一种递归的方法这样做的其它东西一样...
MakeChange(X, x[1..n this is the coins])
for (int i = 1; i < n; i++)
{
if ( (X - x[i] ==0) || MakeChange(X - x[i]) )
return true;
}
return false;
转换这一个动态程序是不会这么容易到我。怎么可能，我方法这个吗？
解决方案
您的代码是一个良好的开端。转换一个递归地解决了动态规划一个通常的方法是做它的“自下而上”而非“自上而下”。也就是说，如果您的递归解决方案计算的东西，使用值较小的X特定的X，则不用计算同样的事情的开始的在较小的X，并把它放在一个表。
在您的情况下，变更MakeChange递归函数成canMakeChange表。
canMakeChange[0] = True
for X = 1 to (your max value):
canMakeChange[X] = False
for i=1 to n:
if X>=x[i] and canMakeChange[X-x[i]]==True:
canMakeChange[X]=True
其他提示
下面我的解决办法是一种贪婪方法计算所有的解决方案和cacheing最新最优的一个。如果当前执行的解决方案已经比中止路径缓存解决方案大。注意，为了获得最佳性能面额应以递减顺序。
import java.util.ArrayList;
import java.util.List;
public class CoinDenomination {
int denomination[] = new int[]{50,33,21,2,1};
int minCoins=Integer.MAX_VALUE;
String path;
class Node{
public int coinValue;
public int amtRemaining;
public int solutionLength;
public String path="";
public List<Node> next;
public String toString() { return "C: "+coinValue+" A: "+amtRemaining+" S:"+solutionLength;}
}
public List<Node> build(Node node)
{
if(node.amtRemaining==0)
{
if (minCoins>node.solutionLength) {
minCoins=node.solutionLength;
path=node.path;
}
return null;
}
if (node.solutionLength==minCoins) return null;
List<Node> nodes = new ArrayList<Node>();
for(int deno:denomination)
{
if(node.amtRemaining>=deno)
{
Node nextNode = new Node();
nextNode.amtRemaining=node.amtRemaining-deno;
nextNode.coinValue=deno;
nextNode.solutionLength=node.solutionLength+1;
nextNode.path=node.path+"->"+deno;
System.out.println(node);
nextNode.next = build(nextNode);
nodes.add(node);
}
}
return nodes;
}
public void start(int value)
{
Node root = new Node();
root.amtRemaining=value;
root.solutionLength=0;
root.path="start";
root.next=build(root);
System.out.println("Smallest solution of coins count: "+minCoins+" \nCoins: "+path);
}
public static void main(String args[])
{
CoinDenomination coin = new CoinDenomination();
coin.start(35);
}
}
只需记忆化步骤添加到递归溶液中，将动态算法落在正确的。下面的例子是在Python：
cache = {}
def makeChange(amount, coins):
if (amount,coins) in cache:
return cache[amount, coins]
if amount == 0:
ret = True
elif not coins:
ret = False
elif amount < 0:
ret = False
else:
ret = makeChange(amount-coins[0], coins) or makeChange(amount, coins[1:])
cache[amount, coins] = ret
return ret
当然，你可以使用一个装饰器自动memoize的，从而导致更自然的代码：
def memoize(f):
cache = {}
def ret(*args):
if args not in cache:
cache[args] = f(*args)
return cache[args]
return ret
@memoize
def makeChange(amount, coins):
if amount == 0:
return True
elif not coins:
return False
elif amount < 0:
return False
return makeChange(amount-coins[0], coins) or makeChange(amount, coins[1:])
请注意：即使非动态编程的版本，你贴有各种边缘的情况下错误的，这就是为什么上面的makeChange稍长比你
此纸是非常相关的： http://ecommons.library.cornell.edu /手柄/6219分之1813
基本上，正如其他人所说，使得最佳变化共计任意面额设定的任意的X是NP难解，这意味着动态编程不会产生及时算法。本文提出了一种多项式时间（即，在输入的大小，这是在以前的算法的改进多项式），用于确定是否贪婪算法总是产生一组给定面额的最佳结果的算法。
下面是C＃版本只供参考找到对于给定的所需金额的硬币的最小数量：
（可参见我的博客@ http://codingworkout.blogspot.com/2014/08/coin-change-subset-sum-problem-with.html 了解详情）
public int DP_CoinChange_GetMinimalDemoninations(int[] coins, int sum)
{
coins.ThrowIfNull("coins");
coins.Throw("coins", c => c.Length == 0 || c.Any(ci => ci <= 0));
sum.Throw("sum", s => s <= 0);
int[][] DP_Cache = new int[coins.Length + 1][];
for (int i = 0; i <= coins.Length; i++)
{
DP_Cache[i] = new int[sum + 1];
}
for(int i = 1;i<=coins.Length;i++)
{
for(int s=0;s<=sum;s++)
{
if (coins[i - 1] == s)
{
//k, we can get to sum using just the current coin
//so, assign to 1, no need to process further
DP_Cache[i][s] = 1;
}
else
{
//initialize the value withouth the current value
int minNoOfCounsWithoutUsingCurrentCoin_I = DP_Cache[i - 1][s];
DP_Cache[i][s] = minNoOfCounsWithoutUsingCurrentCoin_I;
if ((s > coins[i - 1]) //current coin can particiapte
&& (DP_Cache[i][s - coins[i - 1]] != 0))
{
int noOfCoinsUsedIncludingCurrentCoin_I =
DP_Cache[i][s - coins[i - 1]] + 1;
if (minNoOfCounsWithoutUsingCurrentCoin_I == 0)
{
//so far we couldnt identify coins that sums to 's'
DP_Cache[i][s] = noOfCoinsUsedIncludingCurrentCoin_I;
}
else
{
int min = this.Min(noOfCoinsUsedIncludingCurrentCoin_I,
minNoOfCounsWithoutUsingCurrentCoin_I);
DP_Cache[i][s] = min;
}
}
}
}
}
return DP_Cache[coins.Length][sum];
}
在一般情况下，那里的硬币价值可以是任意的，问题呈现被称为 背包的问题, ，而是属于已知的NP-完成(皮尔逊。2004年)，因此是不可解在多项式时，例如动态的程序。
把病例的x[2]=51，x[1]=50,x[0]=1,X=100个。然后它是必需的，算法'考虑'的可能性作出改变，与硬币x[2],或者作出改变初的x[1].第一步使用本国货币，否则被称为 贪婪的算法 -- 以智慧, "使用最大的硬币不到工作，"不会与病理性的派生词.相反，这样的算法的经验一combinatoric爆炸，有资格成NP-完成。
对于某些特别的硬币价值的安排，例如几乎所有那些在实际使用，包括虚构的系统X[i+1]==2*X[i]，有非常快速的算法，甚至O(1)在虚构的情况下，确定最佳的输出。这些算法利用性的币值。
我不知道还有一个动态规划解决方案：一个利用最佳的子解决方案为需要通过编程的主题。在一般的问题只能解决的动态规划如果可以分解成分的问题，当最佳地解决，可以是重新组成一个解决方案，这是可证明是最佳的。也就是说，如果该程序不能从数学上证明("证明")，重新撰写的最优子解决方案的问题，结果在一个最佳的解决方案，然后编程的动态不能适用。
一个例子通常给予的动态规划是一个应用程序乘几个矩阵。根据大小的矩阵，在选择评价 一个·B·C 作为两个等同形式：((一个·B)·C)或(一个·(B·C))会导致计算不同数量的乘法运算和补充。也就是说，一个方法是更优化(更快的)比其他方法。动态规划是一个主题，它以表格形式列出的计算成本的不同方法，以及执行实际计算根据日程安排(或 程序)计算 动态 在运行时间。
一个关键特征是这一计算是根据执行计算时间表而不是由一枚举的所有可能的组合--是否列举为执行递归或迭代地.在例乘以矩阵，在每个步骤中，只有少成本倍增。作为结果，可能成本的中间费用分的最佳计划永远不会计算。换句话说，该时间表的计算不是通过搜索所有可能的时间表是最佳的，而是通过逐步建设一个最佳的时间表从一无所有。
该术语'动态规划'可与'的线性规划'，在其'节目也使用意义上的意义'到的时间表。'
要了解更多关于动态规划，咨询最伟大的书上的算法，尚不得而知我， "算法导论"通过为了在,Leiserson，维斯特和斯坦. "维斯特"是'R'的"RSA"和动态的编程只是一个章节的分数。
如果你在一个递归的方式写的，它是好的，只是使用基于内存的搜索。你必须保存你计算一下，这将不会重新计算
int memory[#(coins)]; //initialize it to be -1, which means hasn't been calculated
MakeChange(X, x[1..n this is the coins], i){
if(memory[i]!=-1) return memory[i];
for (int i = 1; i < n; i++)
{
if ( (X - x[i] ==0) || MakeChange(X - x[i], i) ){
memory[i]=true;
return true;
}
}
return false;
}
