文档介绍：
动态规划例子
篇一：动态规划算法举例分析
动态规划算法
1. 动态规划算法介绍
基本思想是将待求解问题分解成若干子问题，先求解子问题，最终 4 页 共 31 页
i
xi?c
，
。
2
在这个表达式中，须要求xi的值。xi=1表示物品i装入背包中，xi=0表示物品i不装入背包。
考察上述0 / 1背包问题。如前所述，在该问题中须要确定x1，…，xn的值。假设按i = 1，2，…，n 的次序来确定xi 的值。假如置x1 = 0，则问题转变为相对于其余物品（即物品2，3，…，n），背包涵量仍为c 的背包问题。若置x1 = 1，问题就变为关于最大背包涵量为c-w1 的问题。现设r∈{c，c-w1 } 为剩余的背包涵量。
在第一次决策之后，剩下的问题便是考虑背包涵量为r 时的决策。不管x1 是0或是1，[x2 ，…，xn ] 必需是第一次决策之后的一个最优方案，假如不是，则会有一个更好的方案[y2，…，yn ]，因而[x1，y2，…，yn ]是一个更好
n
n
i
的方案。因此最优解符合条件，
?w
i?1
xi?
?w
i?2
i
yi?w1x1?c
。
例：假设n=3, w=[101,14,10], p=[20,18,15], c= 116。若设x1 = 1，则在本次决策之后，可用的背包涵量为r= 116-101=16 。[x2，x3 ]=[0,1] 符合容量限制的条件，所得值为1 5，但因为[x2，x3 ]= [1，0] 同样符合容量条件且所得值为1 8，因此[x2，x3 ] = [ 0，1] 并非最优策略。即x= [ 1，0，1] 可改进为x= [ 1，1，0 ]。若设x1 = 0，则对于剩下的两种物品而言，容量限制条件为11 6。总之，假如子问题的结果[x2，x3 ]不是剩余状况下的一个最优解，则[x1，x2，x3 ]也不会是总体的最优解。
在上述例题的0 / 1背包问题中，最优决策序列由最优决策子序列组成。假设m(i,v) 表示例子中剩余容量为j，剩余物品为i，i+1，…，n 时的最优解的值，即：
3
?vn
m(n,j)??
?0
j?wn0?j?wn
（1）
和
?max?m(i?1,j),m(i?1,j?wi)?vi??
m(i?1,j)
j?wi0?j?wi
m(i,j)??
（2）
因此，m（1，c）是初始时最优问题的最优解。
现在计算xi值，步骤如下：若m(1 ,c) =m( 2 ,c)，则x1 = 0，否则x1 = 1。接下来需从剩余容量c-w1中寻求最优解，用m(2, c-w1) 表示最优解。依此类推，可得到全部的xi (i= 1，2，…，n) 值。 [0/1背包问题的C语言实现算法]
#define N 12
void Knapsack(int v[],int w[],int c,int n,int m[6][N]) {
int i,j,jMax,k;
jMax=(w[n]-1<c?w[n]-1:c); for(i=