0-1背包问题的回溯法中，剪枝用的上界函数问题0-1背包问题的回溯法中，上界函数为什么用单位价值贪心来求，而不是（当前价值+剩余价值

Question

0-1背包问题的回溯法中，剪枝用的上界函数问题
0-1背包问题的回溯法中，上界函数为什么用单位价值贪心来求，而不是（当前价值+剩余价值<=当前最优值） 时剪去右子树。

Answer 1

不知道你哪里看的代码，01背包的分支限界法一般有2种剪枝
1、当去了i后体积超过背包容量，那么剪去该子树，体积都超了价值再大也没用。
2、当前价值+i子树中所有物品的价值<=记录的最优值，应该就是你说的把。
按单位价值贪心虽然不知道你具体指什么，我的理解是i的单位价值很低就剪了，这应该是不对的，万一i后面有个单位价值很高的怎么办。
另外，01背包哪有人会用回溯法啊，这是多么没有效率的算法啊，虽然有剪枝，但时间复杂度还是指数级的啊，你想想如果有10件物品的话，你的叶节点就有1024个了，如果100件的话，我。。。。。。！！