求教一算法（阿里巴巴进山洞取宝）

mayongc

谢谢无双，johnbull

看了些书后想了个算法

首先将问题走个小小的归纳，
a 当最小时只有1件宝物，只有1。1种可能
b 当有2件宝物，有1 ，2，1+2。3种可能，
c 当有3件宝物，有1，2，1+2，   1+3，2+3，1+2+3，3。7种可能。

所以每增加1件宝物就是保留原有的树林，并增加1个新树林（原有的树林+新宝物，及新宝物）
如a到b原有的为1，增加的为1+2，2
b到c原有的为1，2，1+2， 增加的为1+3，2+3，1+2+3，3

这样我就能构造出m件宝物的价值排序，同时用包装n来修正结果来减少穷举的次数。不知道有没有漏洞请大家指正。

无双

但如果这样创建树的话
会不会花费很大
如有100个元素或以上

mayongc

不用建树，关键是在价值的排序。
每增加一个元素，可以利用上一元素的排序结果。只要建立两个链表，互倒就行了，当然开销会很大。

JohnBull

还是我当初的观点——既然只有完全遍历解空间才能找到最优解，我们宁愿使用最“笨”的方法来遍历。
至于提前终止某个节点的继续扩展，可以判断们放弃了多少价值。如果当前节点已经放弃了过多的价值，就不必扩展它下面的节点了。