动态规划讲解.ppth

第一讲 动态规划

(Dynamic Programming)

 动态规划的基本概念和思想

 最短路径问题

 投资分配问题

 背包问题

 排序问题

1

动态规划是运筹学的一个分支，是求解多阶段决策过

2

（总运输费用最小）。

1 2 3 4

5 6

A

C

D

D

E

E

F

5

3

3

6

8

2

1

2

3

3

为

公斤，设有

种物品可供他选择装入包中。已知每种

物品的重量及使用价值（作用），问此人应如何选择携带

的物品（各几件），使所起作用（使用价值）最大？

1 2 … j … n

4

机器负荷分配问题：某种机器可以在高低两种不同的负荷

下进行生产。要求制定一个五年计划，在每年开始时，决

定如何重新分配完好的机器在两种不同的负荷下生产的数

量，使在五年内产品的总产量达到最高。

5