python - 具有有限注释和多个金额的更改制作算法

Question

给定多个金额，以及注释列表(不能重复)。我需要找到音符组合来赠送所有金额。

For Eample: if notes are: [1,1,5,6,6,8,8,10] and amounts are [15, 14, 16].

The solution can be {15:(10,5), 14:(6,8), 16:(1,1,6,8)}

这是变更问题的变体，如 here 所述.下面是使用动态编程解决标准找零问题的代码，给定 V(无限面额的集合)和 C(数量)。如何为非重复票据和多个金额修改它。还需要每个金额的最终组合。

def min_change(V, C):
    m, n = len(V)+1, C+1
    table = [[0] * n for x in xrange(m)]
    for j in xrange(1, n):
        table[0][j] = float('inf')
    for i in xrange(1, m):
        for j in xrange(1, n):
            aC = table[i][j - V[i-1]] if j - V[i-1] >= 0 else float('inf')
            table[i][j] = min(table[i-1][j], 1 + aC)
    return table[m-1][n-1]

更新:

更改制作问题是 NP 完全问题。这里有详细论文http://www.or.deis.unibo.it/kp/Chapter5.pdf尽管如此，还是有一些解决方案是相当优化的并且可以产生结果。

Answer 1

如@MissingNumber 所述，它实际上可能比 NP-complete 更糟糕。子集-子问题会询问是否存在解决方案。该问题被认为是 NP-hard .您的问题实际上问了一些更难的问题，即存在多少种解决方案？此类问题属于P# (P-sharp)复杂度类，我相信它是 P#-complete，至少与 NP-complete 版本一样难(并且可能更难)。

来自维基百科的一些例子来区分这两个类:

An NP problem is often of the form, "Are there any solutions that satisfy certain constraints?"

1. 是否存在加起来为零的整数列表的子集？ (子集和问题)
2. 给定图中是否存在成本小于 100 的哈密顿循环？ (旅行商问题)
3. 是否有满足给定 CNF 公式的变量赋值？ ( bool 可满足性问题)

The corresponding #P problems ask "how many" rather than "are there any". For example:

1. 整数列表中有多少个子集加起来为零？
2. 给定图中有多少哈密顿循环的成本小于 100？
3. 有多少变量赋值满足给定的 CNF 公式？