有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。
输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。
接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数,表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例:
8
解分支界限法中上界(up)的计算和变化是理解该算法的关键。上界的变化反映了在遍历解空间树时,对剩余物品可能价值的重新估计。这个估计随着深入到树的不同层次而变化。
在您提供的例子中,物品已经根据价值与重量的比率排序,即单位重量价值从高到低。这种排序是为了最大化在背包容量限制下的价值。
上界的初始计算
在树的根节点,上界(up)是在背包容量限制下可以获得的最大价值。这通过将物品按单位重量价值排序并贪心地加入背包来估计。在您的例子中:
物品的重量为 [4, 7, 5, 3],价值为 [40, 42, 25, 12],单位重量价值为 [10, 6, 5, 4]。
假设背包容量为 10。
根节点时,上界是在不超过背包容量的情况下,按价值密度从高到低选择物品。因此,先选择重量为 4、价值为 40 的物品(单位价值为 10),剩余容量为 6。然后选择重量为 7、价值为 42 的物品,但由于容量不足,只能部分选择,按比例计算其价值。计算方式为 (42/7) * 6 = 36。因此,初始上界 up = 40 + 36 = 76。
上界的变化
当遍历解空间树时,上界会根据当前节点的情况重新计算。
节点:cp=0, cw=0, up=76
初始状态,上界为 76。
下一层分支:
分支 1: cp=40, cw=4, up=76。这个节点包含第一个物品。剩余容量为 6,剩余的最优选择为部分选择第二个物品,上界仍然为 76。
分支 2: cp=0, cw=0, up=57。这个节点不包含第一个物品。根据剩余物品重新计算上界:首先加入第二个物品(价值 42),剩余容量 3,然后加入第三个物品,但是因为容量不足,只能部分加入,按比例计算其价值 (25/5) * 3 = 15。因此,新的上界 up = 42 + 15 = 57。
再下一层分支(基于分支 1):
分支 1-1: cp=40, cw=4, up=69。这个节点包含第一个物品,不包含第二个物品。剩余容量 6,接下来尝试加入第三个物品。更新后的上界 up = 40 + 25 + (12/3) * 2 = 40 + 25 + 8 = 73(但您提到的是 69,可能是背包容量不同或计算误差)。
分支 1-2: cp=40+42=82, cw=4+7=11(不可行,因为超出背包容量)。
为什么抛弃上界为 57 的分支
在分支界限法中,如果一个节点的上界低于当前已找到的最优解的价值,那么这个节点及其所有子节点都不可能包含比当前最优解更好的解决方案,因此可以被安全地抛弃。在您的例子中,由于上界为 57 的分支的最大可能价值低于其他分支,因此它被抛弃。
您的理解是正确的。让我们详细解释这个过程:
分支2的上界计算
- 分支2 是考虑不将第一个物品(单位价值最高的物品)放入背包的情况。因此,从第二个物品开始计算上界。
- 首先,完整地加入第二个物品(价值 42),因为它的重量(7)小于背包的剩余容量(10)。
- 然后,尝试加入第三个物品,但因为背包剩余容量只有 3(10 - 7 = 3),所以只能部分加入。按照分数背包的逻辑,加入的部分价值为
(25/5) * 3 = 15
。 - 因此,分支2的上界
up = 42 + 15 = 57
。
上界的比较和分支的选择
- 分支1 的上界是 76,而 分支2 的上界是 57。在分支界限法中,我们会比较不同分支的上界,以确定哪些分支可能包含最优解。
- 因为 57 < 76,所以分支2的最大可能价值低于分支1的上界。这意味着即使分支2中所有后续选择都是最优的,它的总价值也不会超过 57,这低于分支1可能达到的价值。
- 因此,根据上界比较,我们选择放弃分支2,转而探索分支1。
递归计算上界
- 是的,每次递归时都需要重新计算上界。上界的计算基于当前节点的状态(包括已经在背包中的物品和背包的剩余容量)。
- 计算上界的逻辑类似于分数背包问题。可以将分数背包的计算方法用于计算上界,尽管在 0-1 背包问题中,我们实际上不会切割物品。
截止条件
- 分支界限法的截止条件是当找到一个叶节点(即考虑完所有物品后的节点),其总价值超过所有其他分支的上界时,这个叶节点的解就是当前的最优解。
- 另一个截止条件是当所有剩余分支的上界都低于当前已知的最优解时,算法结束,因为不可能找到更好的解。
这种方法是一种平衡搜索效率和准确性的策略,它通过计算上界来避免不必要的搜索,而只关注那些可能包含最优解的分支。