0

我正在学习子集和问题，我想在这里问一些问题

(1)子集和算法

刚才看了这个链接的C代码，不知道为什么作者可以定义？

S[i,0]=true ,S[0,j]=false

S[i,0]意味着subset[1,...i]总和0，为什么它可以分配给true.？如果想打印子集的内容，我该如何修改这个算法？因为好像禁止与作者私聊，所以不得不贴出来。

（2）如果数组中有负数，我试图测试它不适合。如何定义和的初始S[i,0]值S[0,j]？

谁能帮我澄清一下？

提前致谢！

4

1 回答 1

1

建议的基本子句有问题，因为有了它，您也可以将s[n,0]其作为初始值。

子集和的递归公式的更好的停止子句是s[i,xi] = true。这个想法很简单，集合{x1,x2,...,xi}包含一个总和为xi的子集 - 它是子集{xi}。递归将稍后处理其余部分，如果有一个子集总和为 0，它将找到它。

根据这种方法，基本条款是：

s[i,xi] = true (for each i)
s[0,j] = false (for each j)

递归公式为：

s[i,j] = s[i-1,j] OR s[i-1,j-xi]

要获取子集中实际存在的元素，您需要遵循使用动态规划构建的矩阵。“遵循”矩阵所做的选择，并坚持一条产生真值的路径，直到找到“停止子句”（s == xi）

它可以递归地描述为：

getSubset(i,s):
   if s[i-1,s]: //there is a solution without choosing xi
       return getSubset(i-1, s)
   if (xi == s): //true base clause
        l <- new list
        l.append(xi)
        return l
   if s[i -1, s-xi]: //there is a solution when choosing xi
        l <- getSubset(i-1,s-xi)
        l.append(xi)
        return l

它很相似（确保你理解为什么）：如何使用背包算法[而不仅仅是包的价值]找到包中的哪些元素？

于 2013-01-03T17:06:05.037 回答