0

给定多个金额，以及笔记列表（您不能重复它们）。我需要找到笔记组合来放弃所有金额。

例如：如果注释是：[1,1,5,6,6,8,8,10]并且金额是[15, 14, 16]。

解决方案可以是{15:(10,5), 14:(6,8), 16:(1,1,6,8)}

这是此处描述的变更问题的变体。下面是使用动态编程解决标准变更问题的代码，给定 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尽管如此，还是有一些解决方案是相当理想的并且可以给出结果。

4

2 回答 2

2

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

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

NP 问题通常具有以下形式：“是否存在满足某些约束的解决方案？”

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

相应的#P 问题询问“有多少”而不是“有没有”。例如：

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

这是 NP 完全问题，请在以下位置找到最佳解决方案：

http://en.wikipedia.org/wiki/Subset_sum_problem

于 2013-04-09T12:29:40.733 回答