数学建模笔记——线性规划

本文最后更新于 8 个月前，文中所描述的信息可能已发生改变。

建立好的模型 ​

• 优化问题：重在模型建立，模型求解
• 数据问题：重在算法应用，结果叙事

比赛流程 ​

1. 选题：你们团队的长处在哪？几个题目的难度配置？预估选题情况？
2. 直奔主题去分析这道题问的是什么
3. 优化问题，尤其是连续优化问题，重点就在于目标函数、约束条件和决策变量

如何建立好的模型 ​

• 不要太在意题目的background
• 知道到底在问什么，知道题目的所问属于哪一类问题才能去联想或者百度到对应的策略
• 往往难就难在目标函数上，抽象成一种我们在视频讲过的也好，实验里做过的也好，在其他地方资料里面看到的也好，总之就是把生问题变成熟问题
• 不要忽略问题之间的联系性，但有时候相对独立的问题是可以并行建模编程的

如何写好目标函数 ​

• 利用线性或非线性关系
• 利用求和和均值形式的函数
• 目标函数与约束条件可能并不独立
• 可能需要用到积分或微分做目标函数
• 多个目标的归一化，使用加权组合、求商等等方法

如何寻找决策变量 ​

见仁见智，但是尽可能在两种情况下选择：

• 如果无法保证取值有穷，那么决策变量尽可能少更好
• 如果能够抽象为0-1规划问题，那就用0-1规划去做

如何写约束条件 ​

• 题目描述
• 常识
• 背景板：文献检索

线性规划模型 ​

运用 python 进行矩阵的运算 ​

import numpy as np

a = np.array([[1, 2, 3], [4, 5, 6]])
b = np.array([[1, 2], [3, 4], [5, 6]])
c = np.array([[1, 2, 3]])
d = np.array([[9, 8, 7], [3, 2, 1]])
# 矩阵加法
sum = a + d
# 放缩
e = 3*a
# 数乘、矩阵乘
e = np.dot(a, b)
# 元素乘
e = a*d
# 转置
e = c.T
e = np.array([[1, 2], [3, 4]])
# 逆矩阵
result = np.linalg.inv(e)
# 行列式
result = np.linalg.det(e)
# 矩阵的秩
e = np.linalg.matrix_rank(d)

运用 python 求一次方程组的解 ​

主要通过scipy sympy numpy这三个库就能实现各种各样的一次方程组求解。sympy主要用于符号解，numpy和scipy主要用于数值解。

例：

$$f(x)=\begin{cases} 10x-y-2z =72 \\ -x +10y -2z =83 \\ -x-y+5z=42 \end{cases}$$

解：

import numpy as np
from sympy import Eq, solve, symbols

A = np.array([[10, -1, -2], [-1, 10, -2], [-1, -1, 5]])  # A为系数矩阵
b = np.array([72, 83, 42])  # b为常数列
inv_A = np.linalg.inv(A)  # A的逆矩阵
x = inv_A.dot(b)  # A的逆矩阵与b做点积运算
x = np.linalg.solve(A, b)  # 5,6两行也可以用本行替代
print(x)

x, y, z = symbols('x y z')
eqs = [Eq(10*x - y - 2*z, 72),
       Eq(-x + 10*y - 2*z, 83),
       Eq(-x - y + 5*z, 42)]
print(solve(eqs, [x, y, z]))

输出：

[11. 12. 13.]
{x: 11, y: 12, z: 13}

线性规划的矩阵形式 ​

• 不等式组条件的矩阵化
• 方程组条件的矩阵化
• 每个变量自己的取值范围
• 目标函数的向量化
• 求极值

目标函数是决策变量的线性组合，有不等关系，等量关系，变量范围，求目标极小值

标准形式 1（规范式、编程使用）：

$$\begin{gather*} \begin{align*} & \ minC^T X & \text{目标函数} \\ & \ \ \ X \end{align*} \\ s.t.\begin{cases} Ax\leq b & \text{不等式组约束条件} \\ Aeq·x=beq & \text{方程组} \\ lb\leq x\leq ub & \text{自变量取值范围} \end{cases} \end{gather*}$$

标准形式 2：

$$\begin{gather*} \begin{align*} & \ \min \ z=C^T X \\ \end{align*} \\ s.t.\begin{cases} A\tilde{x}=b \\ \tilde{x}\geq 0 \end{cases} \end{gather*}$$

如何理解线性规划的标准形式

• 问题是线性的极大值/极小值
• 约束条件本应该是小于等于，这是通用，改等于是利用线性
• 存在不等约束时变换可应用松弛变量
• 规划问题的核心在于决策变量，目标函数和约束条件

线性规划的 python 指令求解 ​

scipy 库求解 ​

例题：

$$\begin{align*} & \ \max\ z=2x_1+3x_2-5x_3 \\ & \ st.\begin{cases} x_1+x_2+x_3=7 \\ 2x_1-5x_2+x_3\geq 10 \\ x_1+3x_2+x_3\leq 12 \\ x_1,x_2,x_3\geq 0 \\ \end{cases} \end{align*}$$

首先转化为标准形式：

$$\begin{align*} & \ \min\ z'=-2x_1-3x_2+5x_3 \\ & \ st.\begin{cases} x_1+x_2+x_3=7 \\ -2x_1+5x_2-x_3\leq -10 \\ x_1+3x_2+x_3\leq 12 \\ x_1,x_2,x_3\geq 0 \\ \end{cases} \end{align*}$$

从上式得出：

• 目标函数系数矩阵：$c=[-2,-3,5]$;
• 约束条件系数矩阵：$A=\begin{bmatrix} -2&5&-1\\ 1&3&1 \end{bmatrix}$ 和 $b=\begin{bmatrix} -10\\12 \end{bmatrix}$

求解代码：

import numpy as np
from scipy.optimize import linprog

c = np.array([-2, -3, 5]) #目标函数
Aeq = np.array([[1, 1, 1]]) #方程组
beq = np.array([7]) #方程组
A = np.array([[-2, 5, -1], [1, 3, 1]]) #不等式组约束条件
b = np.array([-10, 12]) #不等式组约束条件
x1, x2, x3 = (0, None), (0, None), (0, None) #表示0到无穷大

res = linprog(c, A, b, Aeq, beq, bounds=(x1, x2, x3)) #调用
print(res)

输出：

      message: Optimization terminated successfully. (HiGHS Status 7: Optimal)
      success: True
       status: 0
          fun: -14.571428571428571
            x: [ 6.429e+00  5.714e-01  0.000e+00]
          nit: 3
        lower:  residual: [ 6.429e+00  5.714e-01  0.000e+00]
               marginals: [ 0.000e+00  0.000e+00  7.143e+00]
        upper:  residual: [       inf        inf        inf]
               marginals: [ 0.000e+00  0.000e+00  0.000e+00]
        eqlin:  residual: [ 0.000e+00]
               marginals: [-2.286e+00]
      ineqlin:  residual: [ 0.000e+00  3.857e+00]
               marginals: [-1.429e-01 -0.000e+00]
mip_node_count: 0
mip_dual_bound: 0.0
      mip_gap: 0.0

可见：当 $x_1,x_2,x_3$ 分别取：6.429, 0.5714, 0 时，决策变量 $z'$ 取得最小值 -14.571428571428571, 即 $z$ 有最大值 14.571428571428571。

pulp 库求解 ​

例题：

$$\begin{align*} & \ \max\ z=2x_1+3x_2+x_3 \\ & \ st.\begin{cases} x_1+2x_2+4x_3=101 \\ x_1+4x_2+2x_3\geq 8 \\ 3x_1+2x_2\geq 6 \\ x_1,x_2,x_3\geq 0 \\ \end{cases} \end{align*}$$

从上式得出：

• 目标函数系数矩阵：$c=[2,3,1]$;
• 约束条件系数矩阵：$A=\begin{bmatrix} -2&5&-1\\ 1&3&1 \end{bmatrix}$ 和 $b=\begin{bmatrix} -10\\12 \end{bmatrix}$

求解代码：

import pulp

# 目标函数的系数
z = [2, 3, 1]
# 约束
a = [[1, 4, 2], [3, 2, 0]]
b = [8, 6]
# 确定最大化最小化问题，最大化只要把Min改成Max即可
m = pulp.LpProblem(sense=pulp.LpMinimize)
# 定义三个变量放到列表中
x = [pulp.LpVariable(f"x{i}", lowBound=0) for i in [1, 2, 3]]
# 定义目标函数，lpDot可以将两个列表的对应位相乘再加和
# 相当于z[O]*x[O]+z[1]*x[1]+z[2]*x[2]
m += pulp.lpDot(z, x)
# 设置约束条件
for i in range(len(a)):
    m += pulp.lpDot(a[i], x) >= b[i]
# 求解
m.solve()
# 输出结果
print(f"优化结果:{pulp.value(m.objective)}")
print(f"参数取值:{[pulp.value(var)for var in x]}")

输出：

优化结果:7.0
参数取值:[2.0, 0.0, 3.0]

单纯形法 ​

回顾中学阶段，我们求线性规划的时候都是解方程然后直接带点进去，直线与直线之间两两相交就有交点，这其实就是单纯形法的雏形。现在的线性规划方程组是不一定存在交点或者不唯一解的。

线性代数中我们会知道：解方程组的时候是可以用向量和基分解的思想来解决的。单纯形法的思想就是：固定变量，不断变换基向求方程组的解带入，看是不是最优解，不是就更新迭代现阶段的解。

非线性规划模型 ​

非线性问题相比于线性问题 ​

在线性规划的基础上，目标函数可以非线性，限制条件可以非线性，包括非线性的不等式和非线性的等式。

$$\begin{align*} & \ \quad \min \ f(x) & \text{目标函数（可以是非线性）} \\ & \ \begin{cases} Ax\leq b \\ Aeq\cdot x= Beq \\ c(x)\leq 0 \\ Ceq(x)=0 \\ \end{cases} & \text{也可以是非线性} \end{align*}$$

二次规划 ​

二次规划的基本形式 ​

目标函数形式如果是一个二次函数那就是一个二次规划

举例：

$$\begin{gather*} \min f=2x_1^2+3x_1x_3-x_2^2\\ s.t.\begin{cases} x_1^2-2x_2+3x_3=4 \\ x_1+x_2-x_3\leq 6 \\ 2x_1-x_2+x_3\leq 15 \\ x_1, x_2, x_3 > 0 \\ \end{cases} \end{gather*}$$

补充高等数学：拉格朗日乘子法与 KKT ​

在数学最优问题中，拉格朗日乘子法（Lagrange Multiplier，以数学家拉格朗日命名）是一种寻找变量受一个或多个条件限制的多元函数的极值的方法。

这种方法将一个有 n 个变量与 k 个约束条件的最优化问题转换为一个有 n+k 个变量的方程组的极值问题，其变量不受任何约束。

这种方法引入了一种新的标量未知数，即拉格朗日乘数：约束方程的梯度（gradient）的线性组合里每个向量的系数。

$$maximize\ f(x,y)\quad s.t.\quad g(x,y)=0\\ \mathcal{L}(x,y,\lambda)=f(x,y)-\lambda\cdot g(x,y)$$

设目标函数 $f(x)$，不等式约束为 $g(x)$，有时还会添加上等式约束条件 $h(x)$。此时的约束优化问题描述如下:

$$\begin{align*} \min f(x) \\ \begin{cases} h(x)=0 \\ g(x)\leq 0 \\ \end{cases} \end{align*} \qquad \begin{gather*} \mathcal{L}(x,\lambda,\mu)=f(x)+\lambda h(x)+\mu g(x)\\ \begin{cases} \displaystyle\frac{\partial{L}}{\partial{X}}\bigg|_{X=X^*} \\ \lambda \not={0}\\ \mu \geq 0\\ \mu g(X^*)=0\\ h(X^*)=0\\ g(X^*)\leq 0\\ \end{cases} \end{gather*}$$

二次规划的求解 ​

$$\begin{gather*} \begin{gather*} \min\{x_1^2+x_2^2\}\\ s.t.\ x_1+x_2=1;\quad x_2\leq 3 \end{gather*} &\begin{gather*} \text{目标函数是二次函数}\\\text{可以有等式约束和不等式约束} \end{gather*}\\\\ \begin{gather*} \mathcal{L}(x_1,x_2,\lambda,\mu)=x_1^2+x_2^2+\lambda(1-x_1-x_2)+\mu(x_2-3)\\ \end{gather*} &\text{构造拉格朗日函数}\\\\ \begin{align*} \frac{\partial{L}}{\partial{x_i}} & =0,i=1,2\dots \\ x_1 +x_2&=1\\ x_2-3&\leq 0\\ \mu &\geq 0\\ \mu(x_2-3) & = 0. \end{align*}& \begin{gather*} \text{利用KKT条件求解问题}\\\text{是解决约束优化的}\\\bold{\text{通用方法}} \end{gather*} \end{gather*}$$

例：

三台火电机组的运行成本（单位：t/h）与出力限制（单位：MW）分别如下：

$$\begin{align*} F_{G1} & =4+0.3P_{G1}+0.0007P_{G1}^2, & 100\leq P_{G1}\leqq 200 \\ F_{G2} & =3+0.32P_{G2}+0.0004P_{G2}^2, & 120\leq P_{G2}\leqq 250 \\ F_{G3} & =3.5+0.3P_{G3}+0.00045P_{G3}^2, & 150\leq P_{G3}\leqq 300 \\ \end{align*}$$

当负荷为 700MW 时，求经济调度的结果。

求解示例：

# 使用scipy编程
from scipy.optimize import minimize
import numpy as np

def func(x):
    return 10.5+0.3*x[0]+0.32*x[1]+0.32*x[2]+0.0007*x[0]**2+0.0004*x[1]**2+0.00045*x[2]**2

cons=({'type':'eq', 'func':lambda x: x[0]+x[1]+x[2]-700})

b1, b2, b3 = (100, 200), (120, 250), (150, 300)
x0=np.array([100,200,400])
res=minimize(func,x0,method='L-BFGS-B',constraints=cons,bounds=(b1,b2,b3))
print(res)

输出：

message: CONVERGENCE: NORM_OF_PROJECTED_GRADIENT_<=_PGTOL
success: True
 status: 0
    fun: 149.785
      x: [ 1.000e+02  1.200e+02  1.500e+02]
    nit: 2
    jac: [ 4.400e-01  4.160e-01  4.550e-01]
   nfev: 12
   njev: 3
hess_inv: <3x3 LbfgsInvHessProduct with dtype=float64>

# 使用遗传算法编程
from sko.GA import GA


def func(x):
    return 10.5+0.3*x[0]+0.32*x[1]+0.32*x[2]+0.0007*x[0]**2+0.0004*x[1]**2+0.00045*x[2]**2


def cons(x): return x[0]+x[1]+x[2]-700


b1, b2, b3 = (100, 200), (120, 250), (150, 300)
ga = GA(func=func, n_dim=3, size_pop=500, max_iter=500,
        constraint_eq=[cons], lb=[100, 120, 150], ub=[200, 250, 300])
best_x, best_y = ga.run()
print("best x:\n", best_x, "\nbest_y:\n", best_y)

best x:
 [189.4175738  234.68932316 275.89310304]
best_y:
 [312.11124391]

非线性规划案例 ​

非线性规划案例1 ​

某公司有6个建筑工地要开工,每个工地的位置(用平面坐标系a,b表示,距离单位：干米)及水泥日用量d(吨)由下表给出。规划设立两个料场位于A、B,日储量各为20吨。假设从料场到工地之间均有直线道路相连，试确定料场的位置.并制定每天的供应计划,即从A,B两料场分别向各工地运送多少吨水泥,使总的吨干米数最小。

分析：

$$\begin{gather*} \min f=\sum_{i=1}^2\sum_{j=1}^6w_{ij}\sqrt{\left(x_i-a_j\right)^2+\left(y_i-b_j\right)^2}\\ s.t.\begin{cases} \displaystyle\sum_{i=1}^2x_{ij}\geq d_j \\ \displaystyle\sum_{j=1}^6x_{ij}\geq e_i \end{cases} \end{gather*}$$

非线性规划案例2 ​

某单位领导在考虑本单位职工的升级调资方案时，要求相关部门遵守以下的规定：

1. 年工资总额不超过1500000元；
2. 每级的人数不超过定编规定的人数；
3. Ⅱ、Ⅲ级的升级面尽可能达到现有人数的20%；
4. Ⅲ级不足编制的人数可录用新职工，又Ⅰ级的职工中有10%的人要退休.

相关资料汇总于表中，试为单位领导拟定一个满足要求的调资方案。

分析：

为了考虑选取最优的调资方案，需要考虑三个约束条件，显然前两个约束条件为刚性约束，而第三个约束条件为柔性约束。

分别建立目标约束：设由Ⅱ晋升为Ⅰ的人数为x₁，由Ⅲ晋升为Ⅱ的人数为x₂，招聘为Ⅲ的人数为x₃，dn-为未满误差，dn+为过盈误差，n=1,2,3,4,5…

• 为保证调资后的年工资预算仍在指标范围内:

$$\begin{cases} \min\{d_1^+\} \\ 50000(9+x_1)+30000(12-x_1)+20000(15-x_2+x_3)+d_1^--d_1^+=1500000 \end{cases}$$

• 每一级的人数不超过定编规定的人数：

$$\begin{cases} \min\{d_2^++d_3^++d_4^+\} \\ 9+x_1+d_2^--d_2^+=12 \\ 12-x_1+x_2+d_3^--d_3^+=12 \\ 15-x_2+x_3+d_4^--d_4^+=15 \end{cases}$$

• Ⅱ、Ⅲ级的升级面尽可能达到现有人数的20%：

$$\begin{cases} \min \{d_5^--d_5^++d_6^--d_6^+\} \\ x_1+d_5^--d_5^+=3 \\ x_2+d_6^--d_6^+=3 \end{cases}$$

整数规划模型 ​

离散优化和连续优化 ​

离散就是指问题的解或者自变量取值是整数式的，或者说取值是有穷的。连续就是指问题的取值是连续式的，可以是任意的浮点数形式。通常来讲连续问题会比离散问题更容易处理，因为离散问题会考虑到很多限制。

如果给传统的非线性规划或者线性规划加上一个限制就是取值必须是整数，那么问题就是一个离散形式的优化模型。通常我们做离散优化的话整数规划比较多。但从计算机的数值计算方法考虑，连续优化问题的求解又基于离散优化的迭代。

整数规划 ​

全部变量限制为整数的规划问题，称为纯整数规划；部分变量限制为整数的规划问题，称为混合整数规划；变量只取0或1的规划问题，称为0-1整数规划。

1. 分枝定界法：可求纯或混合整数线性规划。
2. 割平面法：可求纯或混合整数线性规划。
3. 隐枚举法：用于求解0-1整数规划，有过滤法和分枝法。
4. 匈牙利法：解决指派问题（0-1规划特殊情形）。
5. 蒙特卡罗法：求解各种类型规划。

0-1规划 ​

进一步，变量取值只能是0或1表示有没有的问题，称为0-1规划问题，是离散规划里面最常见的规划问题。常见问题包括：指派问题、TSP问题和VRP问题、集合覆盖问题······

指派问题的模型 ​

假设$n$个人恰好做$n$项工作，第$i$个人做第$j$项工作的效率为$c_{ij}\geq0$，应指派哪个人完成哪项任务，使完成效率最高。

决策变量：

$$x_{ij}=\begin{cases} 1,&\text{指派第i人完成第j项任务}\\ 0,&\text{不指派第i人完成第j项任务} \end{cases}$$

目标函数：

$$\min Z=\sum_{i}\sum_{j}c_{ij}x_{ij}$$

约束条件：

$$\begin{cases} \displaystyle\sum_{i}x_{ij}=1, & j=1,2,\dots,n & \text{每项任务只能一个人做} \\ \displaystyle\sum_{j}x_{ij}=1, & j=1,2,\dots,n & \text{每个人只能做一项任务} \\ x_{ij}=1\text{或}0 \end{cases}$$

分支定界法 ​

1. 构造初始松弛问题 $S_0$ 及初始松弛问题列表 sList = $[S_0]$
2. 初始化下界 LowerBound = -$\infty$
3. while 松弛问题列表 sList 非空：
   1. 从 sList 中选一个松弛问题 $S_i$（可随机选），并对其使用线性规划方法求解
   2. if $S_i$ 的最优值小于 LowerBound：
      • 直接在 sList 中删除松弛问题 $S_i$，不进行任何分支
   3. elif $S_i$ 的最优解非整数：
      • 按某种规则分支出两个新的松弛问题 $S_{i1}$ 和 $S_{i2}$ ，加入到 sList 中，并删除掉 $S_i$
   4. elif $S_i$ 的最优解为整数：
      • 将下界 LowerBound 更新为S:的最优值
4. LowerBound 即整数规划的最优值，LowerBound 对应的解即整数规划最优解

匈牙利法 ​

匈牙利法的本质是求一个二部图的最大匹配，二部图一边是人，一边是工作，这个匹配就是一组指派方案：

1. 写出人与任务的成本矩阵
2. 成本矩阵每一行减去该行最小值
3. 观察0项是否都不在同一行同一列，如果都不在求解结束
4. 如果有几个0项在同一行或者同一列，观察增广路径十字法做覆盖

实际上就是把没覆盖的十字中没覆盖的行-1，覆盖的列+1。

匈牙利法

例题：

为了便于对模型进行求解与分析，假设有4件事4个人去做，各变对应的B数据假设如表1。

求解代码：

from scipy.optimize import linear_sum_assignment
import numpy as np

T = np.array(
    [
        [25, 29, 31, 42],
        [39, 38, 26, 20],
        [34, 27, 28, 40],
        [24, 42, 36, 23]
    ]
)
row_ind, col_ind = linear_sum_assignment(T)
print(row_ind)
print(col_ind)
print(T[row_ind, col_ind])
print(T[row_ind, col_ind].sum())

输出：

[0 1 2 3]
[0 2 1 3]
[25 26 27 23]
101

动态规划模型 ​

动态规划的基本思想 ​

• 动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法。

• 动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

• 与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。

• 动态规划可以通过填表的方式来逐步推进，得到最优解。

动态规划例题 ​

假设张三要去野营，他准备了以下物品：

每样东西都有相应的价值，可呆呆的他在收拾背包时发现，他的背包最大容量只有6斤，装不下所有的东西，只能从这堆东西中挑选价值最高的物品。

求解代码：

def dynamic_p() -> list:
    # 物品项
    items = [
        {"name": "水", "weight": 3, "value": 10},
        {"name": "书", "weight": 1, "value": 3},
        {"name": "食物", "weight": 2, "value": 9},
        {"name": "小刀", "weight": 3, "value": 4},
        {"name": "衣物", "weight": 2, "value": 5},
        {"name": "手机", "weight": 1, "value": 10}
    ]
    max_capacity = 6                                # 约束条件为 背包最大承重为6
    dp = [[0] * (max_capacity + 1) for _ in range(len(items) + 1)]

    for row in range(1, len(items) + 1):            # row 代表行
        for col in range(1, max_capacity + 1):      # col 代表列
            weight = items[row - 1]["weight"]       # 获取当前物品重量
            value = items[row - 1]["value"]         # 获取当前物品价值
            if weight > col:                        # 判断物品重量是否大于当前背包容量
                dp[row][col] = dp[row - 1][col]     # 大于直接取上一次最优结果 此时row-1代表上一行
            else:
                # 使用内置函数max()，将上一次最优结果 与 当前物品价值+剩余空间可利用价值 做对比取最大值
                dp[row][col] = max(value + dp[row - 1]
                                   [col - weight], dp[row - 1][col])
    return dp


dp = dynamic_p()
for i in dp:  # 打印数组
    print(i)

print(dp[-1][-1])  # 打印最优解的价值和

输出：

[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 10, 10, 10, 10]
[0, 3, 3, 10, 13, 13, 13]
[0, 3, 9, 12, 13, 19, 22]
[0, 3, 9, 12, 13, 19, 22]
[0, 3, 9, 12, 14, 19, 22]
[0, 10, 13, 19, 22, 24, 29]
29

贪心策略 ​

贪心策略简介 ​

贪心算法总是作出在当前看来是最好的选择。也就是说贪心算法并不从整体最优上加以考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，我们希望贪心算法得到的最终结果也是整体最优的。

贪心算法通过一系列的选择来得到一个问题的解。它所作的每一个选择都是当前状态下某种意义的最好选择，即贪心选择。希望通过每次所作的贪心选择导致最终结是问题的一个最优解。这种启发式的策略并不总能奏效，然而在许多情况下确能达到预期的目的。解活动安排问题的贪心算法就是一个例子。下面我们着重讨论可以用贪心算法求解的问题的一般特征。

对于一个具体的问题，我们怎么知道是否可用贪心算法来解此问题，以及能否得到问题的一个最优解呢?这个问题很难给予肯定的回答。但是，从许多可以用贪心算法求解的问题中我们看到它们一般具有两个重要的性质：贪心选择性质和最优子结构性质。

贪心与动态规划的异同 ​

贪心和dp的联系是非常紧密的，我们先来分析一下贪心和dp的不同之处：dp是根据迁移过程的状态去推导下一个过程的状态，是有理论依据的，是讲道理的，通过每次完美的检验而得到最优解，关键是找最优子结构和重复子问题，书上一句原话：dp的子结构必须的独立的，而且是重叠的。

而贪心每次都只顾眼前最优，目光短浅，这种方式是不讲道理的，不像dp一样，还根据前面的迁移状态推导后面的子问题，比如最经典的01背包问题：根据贪心策略，每次放进去的都是目前最优的，即目前价值最大的，直到背包装不下，但是这样放的话肯定是不如人意的，因为没有考虑到背包容量的问题，为什么呢？因为前面说过了，贪心策略只考虑当前最优解，它才不会去考虑什么背包容量的问题呢，它只管装价值最大的物品，这样是得不到最优解的，必须再加一个约束条件：背包容量，那么这个做法就变成了dp的做法了。