非标准硬币最优解的无界背包/硬币更换
我有以下问题：
给定一个目标大小N和一些随机生成的硬币的一些面额，这些硬币存储在数组面额[]中，使用动态规划检查是否存在一个最优解决方案，该方案将使用最少的硬币填充整个目标。
这是硬币兑换问题的一个典型例子，但与现实生活中的货币不同，在现实生活中，每种面额都是经过仔细挑选的，因此可以匹配任何目标。事实并非如此。
我熟悉硬币兑换问题中使用的算法，以及如何构造一个动态规划数组来找到解决方案，但我首先如何检查是否有解决方案？
共有1个答案
让状态用DP[i][sum]表示：使用数组面额的起始i硬币来形成sum的最小硬币数。然后，可将重现性公式化为：
DP[i][sum]= min(DP[i-1][sum],DP[i][sum-denominations[i]]+1)
为什么？第一个DP[i-1][sum]表示仅使用i-1硬币形成sum所需的硬币数量（我们排除第i种面额的情况），另一种情况是当我们包括第i种硬币时（注：我假设我们可以多次包括硬币，这就是我为什么写DP[i][sum面额[i].
现在，基本情况是，DP[i][0]=0
现在，当填充DP表时，您可以很容易地检查DP[n（大小）][sum]是否不等于无穷大，然后存在一个解决方案。。
如果您知道如何构造解决方案（如您所说），您也可以为此解决方案构造解决方案。。
注：对于仅允许一次性包含硬币面额的情况，重复周期更改为
DP[i][sum]= min(DP[i-1][sum],DP[i-1][sum-denominations[i]]+1)
按同样的逻辑！我认为基本情况是一样的！
-
所以我对编码不熟悉，我得到了一个任务，我需要做一个程序，用四分之一、一角、五分和一美分给不到一美元的零钱。然而，作业希望程序打印所需的最低硬币数量（例如，如果我输入58美分，那么输出应该是“2个25美分，1个镍和3个便士”，而不是“2个25美分，0个10美分，1个镍和3个便士”。本质上，如果没有某种硬币，那么程序就不应该打印它）。我一直在想如何制作它，这样程序就不会打印任何不必要的硬币。 这就是我
-
具体而言，问题是： 给定面额数组<代码>硬币[]，每个硬币的限制数组<代码>限制[]和数量<代码>金额，返回所需的最小硬币数量，以获取<代码>金额，或者如果不可能，返回空值。另外，用溶液中使用的每个硬币的数量填充数组 这是我的解决方案： 但它一般不起作用。 我的问题是，例如，在这种情况下： 最佳解决方案是： 并且我的算法给出作为结果。换句话说，它失败了，每当在某种情况下，我将不得不使用比可能的更少
-
动态规划变更问题（有限硬币）。我正在尝试创建一个以以下内容作为输入的程序： 输出： 输出应该是大小为1的数组，其中每个单元格代表我们需要改变单元格索引量的最佳硬币数。 假设数组的单元格位于index： 5，内容为2。这意味着为了给出5（INDEX）的变化，您需要2（单元格的内容）硬币（最佳解决方案）。 基本上，我需要这个视频的第一个数组的输出（C[p]）。这与有限硬币的大区别是完全相同的问题。链接
-
问题：https://leetcode.com/problems/coin-change/ 解决方案：https://repl.it/@Stylebender/HatefulAliceBlueTransverse#index.js 我理解从“按钮式”构建dp阵列解决方案的一般概念流程，但我只是想知道关于第10行： dp[i]=数学。最小值（dp[i]，1 dp[i-硬币[j]]； 当你选择当前的第
-
尝试为一般硬币更换问题编程一个DP解决方案，该解决方案还可以跟踪使用的硬币。到目前为止，我一直在努力给我所需的最低硬币数量，但不知道如何获得使用了哪些硬币以及使用了多少次。我尝试设置另一个表（布尔值），如果硬币被使用，但这似乎不能正常工作。有什么想法吗？
-
我有这样的数据集： 长度：233333450560650780限制：5400 现在我的问题是，从设定的最高长度到最低长度中选择项目，以弥补限制或尽可能接近。 我知道背包和最小硬币兑换都能解决我的问题。我想知道哪个更好。 请注意，硬币变化是使用贪婪算法，背包使用动态编程