我有以下问题：
给定目标大小 N 和存储在数组 denominations[] 中的一些随机生成的硬币的一些面额，使用动态编程检查是否存在最佳解决方案，该解决方案将用最少的硬币数量填充整个目标。
这是硬币找零问题的典型示例，但与现实生活中的货币不同，每种面额都经过仔细挑选，以便可以匹配任何目标，但情况并非如此。
我熟悉硬币找零问题中使用的算法以及如何构造动态编程数组来找到解决方案，但是我如何首先检查是否有解决方案？
问问题
1318 次
1 回答
1
让状态表示为DP[i][sum]：使用数组面额的起始 i 个硬币形成总和的最小硬币数量。那么递归可以表示为：
DP[i][sum]= min(DP[i-1][sum],DP[i][sum-denominations[i]]+1)
为什么？？第一个DP[i-1][sum]表示仅使用 i-1 个硬币形成总和所需的硬币数量（我们排除第 i 个面额的情况），另一种情况是我们包括第 i 个硬币（注意：我假设我们可以包括硬币多次，这就是我写的原因DP[i][sum-denominations[i]].
现在，基本情况，DP[i][0]=0即 NULL 集（对于所有 i 属于从 0 到 n（面额数）！并且DP[0][i]=+INFINITY其中 1<=i<=sum 。
现在当 DP 表被填满时，您可以轻松检查 DP[n(the size)][sum] 是否不等于 +INFINITY 那么是否存在解决方案，否则不...
如果您知道如何构建解决方案（如您所说），您也可以为此解决方案构建解决方案..
PS：为了只允许一次包含硬币面额，重复周期更改为
DP[i][sum]= min(DP[i-1][sum],DP[i-1][sum-denominations[i]]+1)
同样的逻辑！我认为基本情况是一样的！
于 2015-06-16T08:15:51.877 回答