黄金问题
当初有n块黄金，每块黄金的品质为w[i]，小明能够一次性搬运品质不超过m的物体，问小明一次至少能运走多少品质的黄金？
对于该问题，浏览过我之前讲过的深度优先搜寻应该不难写出如下代码。
def dfs(cur, total, status = set()): for i in range(cur, n): if total + w[i] > m: continue status.add(total + w[i]) dfs(i+1, total + w[i]) return status对于w = [1,8,6]，m = 10的数据，能够失去status = {1,8,6,9,7}，也就是w可能组合出的不超过m的所有值，取其最大值即为该问题的答案。
然而该解法的工夫复杂度太高了，为n!（这里还与m值无关，要真有这么大都别玩了），其实这里能够动静布局，咱们如何应答更大n值的状况？
对于规模为10的状况，其复杂度在400w，而对于规模为5的状况，其复杂度在100，也就是说如果咱们可能把一个规模为10的问题分解成两个规模为5的问题，那么工夫复杂度只须要100 + 100 = 200。速度较之前晋升了2万倍。
那么咱们如何通过两个规模为5的解得出规模为10的解呢？
def solution(n, m, w): def dfs(cur, end, total = 0, status = set()): for i in range(cur, end): if total + w[i] > m: continue status.add(total + w[i]) dfs(i+1, end, total + w[i]) return status ans1 = sorted(list(dfs(0, n//2))) ans2 = sorted(list(dfs(n//2, n))) ans = max(ans1) for i in ans2: t = binary_search_last_equal_or_lower(m-i, ans1) ans = max(ans, t+i) return ans上述代码中，咱们遍历ans2列表，在ans1寻找最大的且与i相加不超过m的值（反过来也行），并在遍历的过程中动静更新ans的值，遍历完结，ans即咱们想要的答案。
对于最终的ans，有如下三种可能。
- ans1[i] + ans2[j]
- max(ans1)
- max(ans2)
其中状况1在遍历时实现，状况2在ans赋初值时实现，状况3在ans1没有值能够与m-i结对时实现（这时候二分查找返回0值）。
本文示例题目与acwing 171.送礼物统一，读者可自行尝试提交，验证本人代码的正确性。