求教大神，关于subsetsum

gameboybf2142

最近在看subsetsum的源代码，里面有许多不明白的地方，请教一下各位大神。地址：https://github.com/travisdesell/Subset-Sum
问题1：在generate_subsets.cpp 里面，generate_ith_subset函数的功能是生成第i个集合（集合大小，最大的元素确定），而generate_next_subset是根据现有集合生成下一个集合，这貌似是一种组合数的生成，请问其中的具体原理是什么（我实在看不懂啊）？
问题2：在subset_sum_main.cpp 里面，test_subset函数是用来检验集合的，但我完全看不懂他的算法，是动态规划吗？
求大神解答，不胜感激。

arthur200000

@fwjmath  来自: iPhone客户端

acp134

@fwjmath  
果断到了召唤大神的时间

fwjmath

快要去开会了，先说个梗概……

这种n选k的组合果断是可以有格雷码的（https://zh.wikipedia.org/zh/%E6%A0%BC%E9%9B%B7%E7%A0%81），也就是说，可以将所有组合方式排成一列，使得相邻的组合之间只差一个数。

具体算法的话，貌似有不少。我没仔细看代码，但是我猜他们用了Knuth的计算机程序设计的艺术（TAOCP）第四卷中的算法。手头上没有书，有电子版的话可以直接查。

如果还有问题的话，虽然我也很想详细回答，但也得等我开完会下班了才行……

gameboybf2142

fwjmath 发表于 2013-6-21 14:27
快要去开会了，先说个梗概……

这种n选k的组合果断是可以有格雷码的（https://zh.wikipedia.org/zh/%E6%A0 ...

谢谢大神指教，但我还是有些没明白
1：格雷码只是一种二进制表示数的方法，这和组合数的生成有什么关系？
2：subset_sum_main.cpp 中，是用什么算法实现集合的检验的？

apm46

各种人才...

fwjmath

gameboybf2142 发表于 2013-6-21 21:14
谢谢大神指教，但我还是有些没明白
1：格雷码只是一种二进制表示数的方法，这和组合数的生成有什么关系？ ...

我看了一下代码，他们用的不是格雷码（我说的是广义上的格雷码，也就是说某种生成排列的方法，使得相邻的排列只相差一个元素，二进制的格雷码只是一种特殊情况），而是从小到大的字典序。然后数起来就很方便了，只要看看以某个数字开头的有多少个这样的子集（用nChoosek可以表达出来），如果小于当前的 i，那就说明当前的 i 对应的子集不是以这个数字开头的，将 i 减去子集个数，然后再考虑接下来的子集；如果大于当前的 i，那么当前的 i 对应的子集是以这个数字开头的，填上数字，然后再继续。

其实弄个小例子自己试着跟一下程序，很快就明白的。

然后test_subset显然是动态规划，具体见这里：
http://zh.wikipedia.org/wiki/%E5 ... D%E5%95%8F%E9%A1%8C