我正在复习一些算法课程的老笔记，动态规划问题对我来说似乎有点棘手。 我有一个问题，我们有无限多个硬币，其面值为x1，x2，... xn，我们想要为某个价值X找零。 我们试图设计一个动态程序来确定是否可以找到X的零钱（不是最小化硬币数量或返回哪些硬币，只需true或false）。
我已经思考了这个问题，并且可以看到一种递归方法可以解决这个问题，大致像是......
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
v和一组d硬币面额，该算法的时间复杂度为O(v*d)，并且它使用了O(v)的额外空间。@Heath Hunnicutt说得有道理，你可以通过提前返回来进一步优化这种方法，例如，在canMakeChange[X]=True之后，你可以添加一个额外的条件if (X==v) return true。优化版本将在遇到所有可能的解中的第一个时停止，即使这不是最聪明的找零方式（例如，使用一百个便士找零1英镑）。 - Anthony Accioly我提供的解决方案是一种贪婪方法，计算所有解决方案并缓存最新的最优解。如果当前执行的方案已经大于缓存的方案，则中止该路径。请注意，为了获得最佳性能，货币面额应该按降序排列。
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:])
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];
}
以x [2] = 51，x [1] = 50，x [0] = 1，X = 100为病态例子。然后需要算法“考虑”使用硬币x [2]进行更改的可能性，或者从x [1]开始进行更改。第一步使用国家货币，也称为贪心算法 - “使用小于工作总数的最大硬币”，将无法处理病态硬币。相反，这些算法经历了组合爆炸，使它们成为NP完全问题。
对于某些特殊的硬币价值安排，例如实际使用中的几乎所有硬币价值安排，包括虚构系统X [i + 1] == 2 * X [i]，有非常快速的算法，甚至在虚构情况下是O（1），以确定最佳输出。这些算法利用硬币价值的属性。
我不知道有一个动态规划的解决方案：利用编程模式所需的最优子方案。一般情况下，只有当问题可以分解为子问题时，才能通过动态规划来解决。当这些子问题被最优地解决后，它们可以重新组合成可证明最优的解决方案。也就是说，如果程序员无法在数学上证明重新组合问题的最优子解会导致最优解，则不能应用动态规划。
动态规划的一个常见例子是将多个矩阵相乘的应用。根据矩阵的大小，选择计算A·B·C作为两个等价形式之一：((A·B)·C)或(A·(B·C))，将导致不同数量的乘法和加法计算。也就是说，一种方法比另一种方法更优（更快）。 动态规划是一种模式，它记录不同方法的计算成本，并根据在运行时动态计算的时间表（或程序）执行实际计算。
一个关键特点是按照计算的时间表执行计算，而不是通过枚举所有可能的组合来执行计算——无论是递归还是迭代地执行枚举。在矩阵乘法的例子中，在每个步骤中，只选择最小成本的乘法。因此，从未计算过中间成本次优时间表的可能成本。换句话说，时间表不是通过搜索所有可能的时间表来计算最优时间表，而是通过从零开始逐步构建最优时间表来计算的。
这篇论文非常相关：http://ecommons.library.cornell.edu/handle/1813/6219
基本上，就像其他人所说的那样，使用任意面额集合进行最优找零总数为X是NP难问题，这意味着动态规划无法产生及时的算法。该论文提出了一个多项式时间（也就是输入大小的多项式级别，这是对以前算法的改进）的算法，用于确定贪心算法是否总是针对给定的面额集合产生最优结果。
如果你以递归的方式编写代码，那么可以使用基于内存的搜索。你需要存储已经计算过的结果，这样就不会重复计算了。
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;
}