摘自:https://zhuanlan.zhihu.com/p/136244119
Xi定义为第 i 个物品是否被选择
物品的重量不能够超过背包所能承受的重量。
$$ \sum_{i \in I} w_ix_i < K $$
目标为:所有物品的总价值
$$ \sum_{i \in I} v_ix_i $$ 综上,问题定义如下:
$$ maximize \sum_{i \in I} v_ix_i $$
$$ subject\ to \sum_{i \in I} w_ix_i < K $$
$$ x_i \in \{0,1\} ( i \in I) $$
基本原则:
可将计算过程展开为一颗二叉树,每个i节点由三个元素组成:
分别是:(1)总价值。(目标)(2)总重量。(约束)(3)价值估计。
以上三者可以结合应用于剪枝过程,大幅减少计算量。其中最重要的是价值估计,这对应于松弛概念(Relaxation),松弛得越好,剪枝越有效。
搜索策略:
松弛和搜索是分支定界算法中最重要的主题。