用于修改硬币改变的多项式时间算法
我在考虑硬币改变时想到了以下问题，但我不知道有效的（伪多项式时间）算法来解决它。 我想知道是否有任何伪多项式时间解决方案，或者是否有一些我错过的经典文献。
有一个众所周知的伪多项式时间动态规划解决方案的硬币更换问题，其中要求如下：
你有 硬币， 其中有一个值 。 存在多少个硬币子集，使得硬币值的总和为 ？
动态编程解决方案运行于 ，并且是一个经典。 但我对以下轻微概括感兴趣：
如果 硬币不再具有价值 ，而是可以假设一组 值 ？ 现在问题是：存在多少个硬币子集，例如存在将硬币分配给值以使得这些硬币的值的总和为 ？
（经典的硬币更换问题实际上是这个问题的一个实例 对全部 ，所以我不期望多项式时间解决方案。）
例如，给出 和 ，以及下列硬币：
然后，有 子集：
我遇到的问题恰恰是第三种情况; 很容易修改这个问题的经典动态编程解决方案，但它会将这两个子集计数分开，因为分配了不同的值，即使所采用的硬币是相同的。
到目前为止，我只能找到这个问题的直接的指数时间算法：考虑每一个 子集，并运行标准的动态编程硬币更改算法（即 ）检查这个硬币的子集是否有效，给出一个 时间算法。 这不是我在这里寻找的; 我试图找到一个没有问题的解决方案 因子。
你能否提供一个伪多项式时间算法来解决这个问题，或者可以证明，除非P = NP，否则不存在？ 也就是说，这个问题是NP完全（或类似的）。
也许这很难，但你问这个问题的方式似乎并不那么容易。
拿硬币1和3，分别分别为7和3，或分别为6和4，这些都被认为是相同的方式。
让我们以这种方式编码两个等价的解决方案：
现在，当我们记录一个解决方案时，我们不能问问该对的第一个元素（1,3）是否已经解决了吗？ 然后我们将抑制计算（6，4）解。
链接地址: http://www.djcxy.com/p/70677.html