一、概念
动态规划算法是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。动态规划算法的基本思想与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。
由于动态规划解决的问题多数有重叠子问题这个特点,为减少重复计算,对每一个子问题只解一次,将其不同阶段的不同状态保存在一个二维数组中。
比较有趣的一句话是:每个动态规划都从一个网格开始。
问题 ==> 子问题 ==> 子问题最优解 ==> 问题最优解
二、思路
1.分析最优解的性质,并刻画其结构特征。
2.递归的定义最优解。
3.以自底向上或自顶向下的记忆化方式(备忘录法)计算出最优值。
4.根据计算最优值时得到的信息,构造问题的最优解。
三、特性
- 最优化原理:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。
- 无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。
- 有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势)
四、应用
0-1背包问题
题目:
给定n种物品和一个背包,物品i的重量为wi,价值为vi,背包的容量为c。问:应该如何选择装入背包中的物品,使得装入背包中物品的总价值最大?
分析:
0-1背包问题
代码:
#include<stdio.h>
#define MAX 100
int n; // 描述物品个数
int c; // 描述背包容量
int value[MAX]; // 描述物品价值
int weight[MAX]; // 描述物品重量
int main() {
// 初始赋值操作
value[0] = 1500;
value[1] = 3000;
value[2] = 2000;
weight[0] = 1;
weight[1] = 4;
weight[2] = 3;
c = 4;
n = 3;
// 构造最优解的网格:3行4列
int maxValue[MAX][MAX];
for (int i = 0; i < n; i++) {
for (int j = 0; j < c; j++) {
maxValue[i][j] = 0;
}
} // end for
// 填充网格
for (int i = 0; i < n; i++) {
for (int j = 1; j <= c; j++) {
if (i == 0) {
maxValue[i][j - 1] = (weight[i] <= j ? value[i] : 0);
} else {
int topValue = maxValue[i - 1][j - 1]; // 上一个网格的值
int thisValue = (weight[i] <= j ? // 当前商品的价值 + 剩余空间的价值
(j - weight[i] > 0 ? value[i] + maxValue[i - 1][j - weight[i]] : value[i])
: topValue);
// 返回 topValue和thisValue中较大的一个
maxValue[i][j - 1] = (topValue > thisValue ? topValue : thisValue);
} // end if
} // end inner for
} // end outer for
// 打印结果二维数组maxValue
for (int i = 0; i < n; i++) {
for (int j = 0; j < c; j++) {
printf("%6d", maxValue[i][j]);
}
printf("\n");
}
return 0;
}
网友评论