分支定界法求解大象子集优化问题：枚举所有可行解

这是《高级算法》课程的往届考试真题，3小时考试中占5分，预计1小时完成，目前在第一问求解上遇到困难。

问题描述 #

已知n≥2头大象，每头大象用三元组(weight(i), intelligence(i), cost(i))表示，其中每头大象的体重、智力和成本均唯一。目标是找到满足以下两个条件的大象子集S：

1. 对于S中的任意i、j，weight(i) < weight(j) ⇨ intelligence(i) < intelligence(j)，反之亦然；
2. 最大化子集S的成本总和Σcost(i)。

大象数据 #

问题1：使用分支定界法求解最优解，需枚举所有可能的可行解 #

尝试代码（缺少最外层循环） #

S = [ [2300, 7,10], [2000, 14,80], [2800, 13,40], [2100, 11,50], [2500, 6,20], [2600, 9,15] ]

solution = [ [i] for i in range(1,7)]
# for loop here 
for i in range(len(S)):

    for j in range(i+1, len(S)):

        if (S[i][0] < S[j][0] and S[i][1] < S[j][1]) or (S[i][0] > S[j][0] and S[i][1] > S[j][1]) : 

            solution.append( [ i+1, j+1 ])

    solution.pop(0)

预期输出 #

[[1,3], [1,6], [3,4], [3,5], [3,6], [5,6], [1,3,6],[3,5,6]]

期望分步执行结果 #

第一次循环结束后，solution的结果应为：

solution = [ [1,3] , [1,6] , [3,4], [3,5], [3,6], [5,6]]

第二次循环仅检查并扩展已有组合：

• 针对[1,3]，尝试添加4、5、6（因为[3,4]、[3,5]、[3,6]是可行组合）；
• 针对[3,5]，尝试添加6（因为[5,6]是可行组合）。

目前困惑：感觉应该用递归实现，但不知道如何转化为代码，甚至不确定当前的思路是否正确。恳请提供解题思路、正确解法或代码修正建议。

内容的提问来源于stack exchange，提问作者Solal Peiffer-Smadja