数对数组b总和不超过限制时求a最大总和应使用哪种算法

这个场景属于典型的0-1背包问题，可根据数据规模选择对应解法：

• 常规动态规划解法：适用于b的总和阈值数值不大的场景。将每个数对(a,b)对应为背包问题的物品：a为物品价值，b为物品重量，给定阈值为背包最大承重，时间复杂度为O(n*W)，n为数对总数量，W为b的总和阈值。
  你给出的测试用例用该方法即可快速得到正确结果：

输入数对：[(3,2),(100,10),(85,12),(65,5),(120,25),(50,10),(35,5),(150,20)]，b总和阈值为20
最优解最大a总和为200，对应选中数对[(100,10),(65,5),(35,5)]

• 折半搜索（meet-in-the-middle）解法：如果b的阈值极大，动态规划的空间、时间成本不可接受，且数对总数量不超过40时可采用该方法，时间复杂度为O(n*2^(n/2))。
• 近似解法：如果允许少量误差、需要极致性能，可使用贪心策略或背包近似算法，大幅降低运算成本。

内容的提问来源于stack exchange，提问作者Moha