无界knapsack/coin 非标币最优解变化
Unbounded knapsack/coin change with optimal solution for non-standard coins
我有以下问题：
Given a target size N and some denominations of some randomly
generated coins stored in array denominations[] check using dynamic
programming if there is an optimal solution which will fill the entire
target with the least amount of coins used.
这是硬币找零问题的一个典型例子，然而与现实生活中的货币不同，每个面额都经过仔细挑选，以便可以匹配任何目标，情况并非如此。
我熟悉硬币找零问题中使用的算法以及如何构造动态规划数组来找到解决方案，但我如何首先检查是否有解决方案？
让状态表示为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 集（对于从 0 到 n（面额数量）的所有 i！和 DP[0][i]=+INFINITY 其中 1<=i<=sum .
现在当 DP table 被填满时，你可以很容易地检查 DP[n(the size)][sum] 是否不等于 +INFINITY 然后有一个解决方案，否则不。
如果你知道如何构建一个解决方案（如你所说），你也可以为这个解决方案构建解决方案..
P.S。 : 为了只允许一次包含硬币面额，循环更改为
DP[i][sum]= min(DP[i-1][sum],DP[i-1][sum-denominations[i]]+1)
同理！我认为基本情况将相同！
我有以下问题：
Given a target size N and some denominations of some randomly generated coins stored in array denominations[] check using dynamic programming if there is an optimal solution which will fill the entire target with the least amount of coins used.
这是硬币找零问题的一个典型例子，然而与现实生活中的货币不同，每个面额都经过仔细挑选，以便可以匹配任何目标，情况并非如此。
我熟悉硬币找零问题中使用的算法以及如何构造动态规划数组来找到解决方案，但我如何首先检查是否有解决方案？
让状态表示为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 集（对于从 0 到 n（面额数量）的所有 i！和 DP[0][i]=+INFINITY 其中 1<=i<=sum .
现在当 DP table 被填满时，你可以很容易地检查 DP[n(the size)][sum] 是否不等于 +INFINITY 然后有一个解决方案，否则不。
如果你知道如何构建一个解决方案（如你所说），你也可以为这个解决方案构建解决方案..
P.S。 : 为了只允许一次包含硬币面额，循环更改为
DP[i][sum]= min(DP[i-1][sum],DP[i-1][sum-denominations[i]]+1)
同理！我认为基本情况将相同！