为什么0-1背包递归代码中max<0时需返回INT_MIN而不能使用0

max < 0 边界触发的本质是当前选择的物品总重量已经超过背包容量，属于非法解分支，不能参与最优解的竞争，两个返回值的差异就是对非法分支的处理逻辑不同： #

返回INT_MIN的正确逻辑 #

INT_MIN是C++整型的最小值，当非法分支返回该值时，上层计算include = v[n] + 递归返回值的结果仍然是极小的负数，和代表合法分支的exclude值比较时，必然会被判定为更小值直接淘汰，完全不会干扰最优解的选择。

返回0的错误逻辑 #

如果此处返回0，相当于默认「超重的非法分支可以获得0价值」，但上层计算include时会把当前物品的价值v[n]加上这个0，最终得到的include = v[n]相当于你拿了当前物品的全部价值，却没有扣除它的重量成本，相当于凭空捏造了一个不存在的合法解。 #

你的测试用例错误复现 #

你得到的错误结果65对应的是25 + 40的价值组合，对应的重量是4 + 8 = 12，已经超过背包容量10：

• 选择重量为4的25价值物品后，剩余容量为6，再尝试选择重量为8的40价值物品时，剩余容量6 - 8 = -2触发max < 0边界
• 若边界返回0，include计算结果为40 + 0 = 40，加上上层的25就得到65，这个非法解被当成合法解参与比较，最终得到错误结果
• 若边界返回INT_MIN，include = 40 + INT_MIN是极小负数，会直接被排除，不会参与竞争，最终得到合法最优解60。

补充说明：该逻辑仅在所有物品价值为正的场景下生效，如果存在负价值物品，需要根据场景调整非法分支的返回值。

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