c - 如何理解子集和问题

Question

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

(1) Subset Sum algorithm

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

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

S[i,0] 表示求和为0的subset[1,...i],为什么可以赋值到true。？如果想打印子集的内容，我该如何修改这个算法？因为好像不能跟作者私聊，所以只好贴出来了。

(2)如果数组中有负数，我试过不适合。如何定义S[i,0]和的初始值S[0,j]?

谁能帮我解释一下？

提前致谢!

Answer 1

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

subset-sum 递归公式的一个更好的停止子句是 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]

---

要获得哪些元素实际上在子集中，您需要遵循您使用动态规划构建的矩阵。 “遵循”矩阵所做的选择，并坚持一条产生 true 的路径，直到找到“停止子句”(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

它很像(确保你明白为什么):How to find which elements are in the bag, using Knapsack Algorithm [and not only the bag's value]?