我正在回顾我的算法课程中的一些旧笔记，动态编程问题对我来说似乎有点棘手。我有一个问题，我们有无限供应的硬币，有一些面额 x1，x2，... xn，我们想找一些价值 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
我下面的解决方案是一种贪婪的方法，计算所有解决方案并缓存最新的最优解决方案。如果当前执行的解决方案已经大于缓存的解决方案，则中止路径。请注意，为获得最佳性能，面额应按降序排列。
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
当然，您可以使用装饰器来自动记忆，从而获得更自然的代码：
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 比您的稍长。
在一般情况下，硬币值可以是任意的，您提出的问题称为背包问题，并且已知属于 NP-complete ( Pearson, D. 2004 )，因此无法在多项式时间内解决，例如动态规划。
以 x[2] = 51, x[1] = 50, x[0] = 1, X = 100 的病态例子为例。那么需要算法“考虑”用硬币 x[2 找零的可能性]，或者从 x[1] 开始进行更改。用于国家造币的第一步，也称为贪心算法——也就是说，“使用小于工作总量的最大硬币”将不适用于病态造币。相反，这样的算法经历了组合爆炸，使它们符合 NP-complete 的条件。
对于某些特殊的硬币价值安排，例如实际上所有实际使用的，包括虚拟系统 X[i+1] == 2 * X[i]，有非常快的算法，甚至在虚拟系统中 O(1)给定的情况，以确定最佳输出。这些算法利用硬币价值的属性。
我不知道动态编程解决方案：一种利用编程主题所需的最佳子解决方案的解决方案。一般来说，一个问题只能通过动态规划来解决，如果它可以分解为子问题，当优化解决时，可以重新组合成一个可证明是最优的解决方案。也就是说，如果程序员不能在数学上证明（“证明”）重新组合问题的最优子解会产生最优解，则不能应用动态规划。
动态规划的一个常见示例是多个矩阵相乘的应用。根据矩阵的大小，选择将A · B · C评估为两种等价形式中的一种：(( A · B )· C ) 或 ( A ·( B · C )) 会导致不同的计算乘法和加法的数量。也就是说，一种方法比另一种方法更优化（更快）。动态规划是将不同方法的计算成本制成表格的主题，并根据动态计算的时间表（或程序）执行实际计算在运行时。
一个关键特性是计算是根据计算出的调度执行的，而不是通过枚举所有可能的组合——无论枚举是递归执行还是迭代执行。在矩阵相乘的例子中，在每一步，只选择成本最低的乘法。因此，永远不会计算中间成本次优计划的可能成本。换句话说，调度不是通过搜索所有可能的调度以获得最优调度来计算的，而是通过从无到有逐步构建最优调度来计算的。
命名法“动态规划”可以与“线性规划”相比较，其中“程序”也用于“调度”的含义。
要了解有关动态编程的更多信息，请参阅我所知道的关于算法的最伟大的书籍，Cormen、Leiserson、Rivest 和 Stein 的“算法简介”。 “Rivest”是“RSA”的“R”，而动态规划只是乐谱的一章。
这篇论文非常相关：http ://ecommons.library.cornell.edu/handle/1813/6219
基本上，正如其他人所说，用任意面额集对任意 X 进行总计的最优更改是 NP-Hard，这意味着动态规划不会产生及时的算法。本文提出了一种多项式时间（即输入大小的多项式，这是对先前算法的改进）算法，用于确定贪心算法是否总是为给定的面额集产生最佳结果。
这是 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];
}
i如果您以递归方式编写，那很好，只需使用基于内存的搜索即可。您必须存储您计算的内容，不会再次计算
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;
}