算法题：变形背包问题，给定 n 个物品的重量 wi、价值 vi 和背包容量 m，其中 1

Question

算法题：变形背包问题，给定 n 个物品的重量 wi、价值 vi 和背包容量 m，其中 1 <= n <= 40，0 <= wi, vi, m <= 10^15，如何求解最大总价值？

Accepted Answer

考察点：考察大规模背包问题的算法设计与复杂度分析。回答思路：识别n≤40但容量和价值极大的特点，排除常规DP 提出折半枚举（Meet in the Middle）思路 正确设计前半和后半的组合枚举，并处理容量约束 说明二分查找或双指针优化合并过程

算法题：变形背包问题，给定 n 个物品的重量 wi、价值 vi 和背包容量 m，其中 1 <= n <= 40，0 <= wi, vi, m <= 10^15，如何求解最大总价值？