• 每个问题都有多种贪婪算法
• 在遇到一个新问题时，可首先采用贪婪算法作为Baseline。

Xi定义为第 i 个物品是否被选择

• 当 Xi = 1时，代表物品被选择
• 当 Xi = 0 时，代表物品不被选择

物品的重量不能够超过背包所能承受的重量。

$$ \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），松弛得越好，剪枝越有效。

搜索策略：

• depth-first, best-first, least-discrepancy
• many others

松弛和搜索是分支定界算法中最重要的主题。