摘自：[https://zhuanlan.zhihu.com/p/136244119](https://zhuanlan.zhihu.com/p/136244119)

# 1. Greedy Algorithm

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

# 2. Modeling

## （1）决策变量 （Decision Variables）

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

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

## （2）问题限制（Problem Constraint）

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

$$
\sum_{i \in I} w_ix_i < K
$$

## （3）目标函数（Objective Function）

目标为：所有物品的总价值

$$
\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)
$$

## 3. 动态规划（Dynamic Programming）

基本原则：

- 分而治之
- 自下而上的计算

## 4. 分支定界（Branch and Bound）

可将计算过程展开为一颗二叉树，每个i节点由三个元素组成：

分别是：（1）总价值。（目标）（2）总重量。（约束）（3）价值估计。

以上三者可以结合应用于剪枝过程，大幅减少计算量。其中最重要的是价值估计，这对应于松弛概念（Relaxation），松弛得越好，剪枝越有效。

搜索策略：

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

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