首页 文章

修正硬币变换的伪多项式时间算法

提问于
浏览 次
1

在考虑硬币改变时我想到了以下问题，但我不知道有效（伪多项式时间）算法来解决它 . 我想知道是否有任何伪多项式时间解决方案，或者可能是我遗漏的一些经典文献 .

有一个众所周知的解决硬币变化问题的方法，它要求如下：

你有
n
个硬币，
ith
的值为
vi
. 存在多少个硬币子集，这样硬币值的总和就是
W
？

动态编程解决方案在
O(nW)
中运行，是经典的 . 但是我对以下几点概括感兴趣：

如果
ith
硬币不再仅具有
vi
的值，而是可以假设一组
l_i
值
vi = {vi1, vi2, vi3, ..., vili}
怎么办？现在，问题是：存在多少个硬币子集，这样就存在硬币分配给值，这样这些硬币的总和就是
W
？

（对于所有
i
，经典硬币更改问题实际上是
li = 1
的这个问题的一个实例，所以我不期望多项式时间解决方案 . ）

例如，给定
n = 3
和
W = 10
，以及以下硬币：

l1 = 4, v1 = {3, 6, 7, 10}

l2 = 2, v2 = {1, 10}

l3 = 2, v3 = {3, 4}

然后，有
4
子集：

  • 仅使用硬币
    1
    ，将此硬币指定为值
    10
    .

  • 仅使用硬币
    2
    ，将此硬币指定为值
    10
    .

  • 拿硬币
    1
    和
    3
    ，分别赋予它们
    7
    和
    3
    的值 or
    6
    和
    4
    -这些被认为是相同的方式 .

  • 取硬币
    1
    ，
    2
    和
    3
    ，并将它们分别赋值为
    6
    ，
    1
    和
    3
    .

我遇到的问题恰恰是第三种情况;修改这个问题的经典动态编程解决方案很容易，但是它会将这两个子集统一为单独因为分配了不同的值，即使所用的硬币是相同的 .

到目前为止，我只能找到这个问题的直接指数时间算法：考虑每个
2^n
子集，并运行标准动态编程硬币更改算法（这是
O(nW^2)
）来检查这个硬币子集是否有效，给出
O(2^nnW^2)
时间算法 . 那个's not what I'米在这里寻找;我试图找到一个没有
2^n
因子的解决方案 .

您能否为我提供一个伪多项式时间算法来解决这个问题，或者可以证明它不存在，除非P = NP？也就是说，这个问题是NP完全的（或类似的） .

algorithm dynamic-programming coin-change

1 回答

  • 0

    也许这很难，但你问这个问题的方式似乎并非如此 .

    取硬币1和3，分别赋予它们分别具有值7和3或分别为6和4 - 这些被认为是相同的方式 .

    让我们用这种方式编码两个等价的解决方案：

    • （（1,3），（7,3））

    • （（1,3），（6,4））

    现在，当我们记住一个解决方案时，我们不能只问这对中的第一个元素（1,3）是否已经解决了？然后我们将抑制计算（6,4）解决方案 .

    回复于

相关问题