华为题库已更新至:华为实习&秋招真题题库请移步。

该题可以使用状态压缩动态规划（DP）或深度优先搜索（DFS）结合二分查找来解决。由于背包容量可达到 10^9，而物品数量 n 为 40，使用普通的 01 背包算法显然不可行，因为 2^40 的复杂度会爆炸。因此，我们可以将物品分成两个组，每组最多有 20 个物品，这样总的复杂度将减少到 2^20，大约在 100 万级别，仍然可以接受。

具体思路如下：

1.对于每个组，使用状态压缩 DP 或 DFS 计算出所有可能的组合（重量和价值）。$\\$ 2.枚举第一个组的每个组合 x，然后利用二分查找找到第二组中最接近 T - x 的组合 y。$\\$ 3.更新答案为 ans = max(ans, x + y)。$\\$ 整体时间复杂度为 O((2^(n/2)) log(2^(n/2)))，这样就能高效地解决问题。 这样做的好处是大幅降低了复杂度，同时利用二分查找加速了查找过程，使得计算更为高效。

代码如下