那一年， 非计算机专业的我听到0-1背包和动态规划， 觉得很高大上， 其实， 动态规划无非就是寻找高中数学中所说的递推公式而已。最近又复习到0-1背包问题和动态规划， 所以打算用代码来玩玩。
0-1背包问题： 一个小偷来出来活动了， 拿了一个背包， 最多可以装50斤的东西的小袋子。 他眼睛一亮， 发现了三件宝贝a, b, c. 其中a重10斤， 价值60元; b重20斤， 价值100元; c重30斤， 价值120元。 问： 在背包允许的范围内， 小偷最多能偷到多少钱？
有的人要说了， 这还不简单， 100 + 120 = 220不就是最大值么？ 可是， 这是简单的情况啊， 当宝贝多了后， 还能一眼看出么？ 有的人可能说， 穷举啊，我勒个去。 还是来看看动态规划吧。所谓动态规划， 实际上即使动态考虑， 也就是寻找递推公式， 别无其他。
本想写个递推公式， 可是这CSDN写公式不太方便，， 所以还是算了。 一旦有了递推公式， 要计算值， 那是计算机的长项， 直接给出代码吧， 代码蕴含一切（50斤=5十斤， 以十斤为一个单位， 方便编程）：
#include<iostream>using namespace std; #define N 3 // N件宝贝#define V 5 // C是背包的总capacityint main() { int value[N + 1] = {0, 60, 100, 120}; // 钱啊int weight[N + 1] = {0, 1, 2, 3}; // 重量int f[N + 1][V + 1] = {0}; // f[i][j]表示在背包容量为j的情况下， 前i件宝贝的最大价值int i = 1;int j = 1;for(i = 1; i <= N; i++){for(j = 1; j <= V; j++){// 递推关系式出炉if(j < weight[i]){f[i][j] = f[i – 1][j];}else{int x = f[i – 1][j];int y = f[i – 1][j – weight[i]] + value[i];f[i][j] = x < y ? y : x;}}}for(i = N; i >= 1; i–){for(j = 1; j <= V; j++){printf("%4d ", f[i][j]);}cout << endl;}return 0; } 结果：
60 100 160 180 220 60 100 160 160 160 60 60 60 60 60
我们也很容易求出了220, 当然，上述程序只告诉了价值的最大值， 并没有告诉小偷怎么去选择才能最大化价值。 实际上， 如果要告诉小偷怎么选择， 那也很简单， 再搞个数组记录一下即可， 也就不再赘述了。
动态规划。哪里来的动态呢？ 本来是f[3][5], 硬生生得让静止的f[3][5]变成了动态的f[i][j], 这就是所谓的动态。 哪里来的规划呢？ 其实没啥规划， 只不过是划分一下而已。可见，动态规划， 无非就是高中数学讲的递推公式而已， 在大学的《信号与系统》中， 又叫状态转移方程。
动态规划，看似高端， 其实不过如此。
最后， 我们再来看个几乎完全一致的问题：物品个数n=5,物品重量w[5]={2，2，6，5，4},物品价值v[5]={6，3，5，4，6}, 背包的最大容量为10，求价值最大化。
代码如下：
#include<iostream>using namespace std; #define N 5 // N件宝贝#define V 10 // C是背包的总capacityint main() { int value[N + 1] = {0, 6, 3, 5, 4, 6}; // 钱啊int weight[N + 1] = {0, 2, 2, 6, 5, 4}; // 重量int f[N + 1][V + 1] = {0}; // f[i][j]表示在背包容量为j的情况下， 前i件宝贝的最大价值int i = 1;int j = 1;for(i = 1; i <= N; i++){for(j = 1; j <= V; j++){// 递推关系式出炉if(j < weight[i]){f[i][j] = f[i – 1][j];}else{int x = f[i – 1][j];int y = f[i – 1][j – weight[i]] + value[i];f[i][j] = x < y ? y : x;}}}for(i = N; i >= 1; i–){for(j = 1; j <= V; j++){printf("%4d ", f[i][j]);}cout << endl;}return 0; } 结果为：
0 6 6 9 9 12 12 15 15 15 0 6 6 9 9 9 10 11 13 14 0 6 6 9 9 9 9 11 11 14 0 6 6 9 9 9 9 9 9 9 0 6 6 6 6 6 6 6 6 6
可见， 最大值为15， 不多说。
版权声明：本文为博主原创文章，未经博主允许不得转载。
要做一个积极勇敢乐观的追梦人，永远不说消极的话，
