c - 带集合的动态规划

Question

我在动态编程中有一个典型的问题。

我的问题是一个数组 = {1,2,3,4,5,6}，我必须找到总和最多为 k 的所有数组。如果我考虑所有集合，它将成为指数算法。我想通过动态编程来实现这一点。

Suppose f k =7,
My idea is 
Pass 1: {1],{2}....{6}
Pass 2: Pass1 + {1,2},{1,3},{1,4},{1,5}
Pass 3: Pass2 + {1,2,3},

我的算法停止了。

我无法用动态编程来制定这个。有输入吗？？如何将此算法制定为程序？

Answer 1

该问题的 DP 解决方案应遵循下一个递归公式，并自下而上构建：

f(i,0) = {{}} //a set containing only an empty set
f(0,W) = {{}} (W > 0)
f(0,W) = {} (W < 0) //an empty set
f(i,W) = f(i-1,W) [union] extend(f(i-1,w-element[i]),element[i])

其中函数 extend(set,e) 是：

extend(set,e):
   for each s in set: //s is a set itself
      s.add(e) 

请注意，复杂性仍然可能是指数的（甚至不是伪多项式），因为生成的集合数可能是指数的，并且存储在 DP 表中。

Answer 2

您的问题是背包问题的一个实例，其相关的决策问题已知是 NP 完全的。这意味着肯定不会有次指数算法（尽管缺少数学证明）。

ZachLangleys 的评论表明，即使有一个有效的问题求解器，所有解决方案的枚举在最坏的情况下仍然是指数的，因为产生输出已经需要指数时间。

由于决策问题是 NP 完全的，因此计数不会更容易（否则您将计数并随后测试结果是否等于 0）。