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 表中。