版权所有，转载请注明出处！
动态规划是用空间换时间的一种方法的抽象。其关键是发现子问题和记录其结果。然后利用这些结果减轻运算量。
比如01背包问题。
/* 一个旅行者有一个最多能用M公斤的背包，现在有N件物品，
它们的重量分别是W1，W2，...,Wn,
它们的价值分别为P1,P2,...,Pn.
若每种物品只有一件求旅行者能获得最大总价值。
输入格式：
M,N
W1,P1
W2,P2
......
输出格式：
X
*/
因为背包最大容量M未知。所以，我们的程序要从1到M一个一个的试。比如，开始任选N件物品的一个。看对应M的背包，能不能放进去，如果能放进去，并且还有多的空间，则，多出来的空间里能放N-1物品中的最大价值。怎么能保证总选择是最大价值呢？看下表。
测试数据：
10,3
3,4
4,5
5,6
c[i][j]数组保存了1,2,3号物品依次选择后的最大价值.
这个最大价值是怎么得来的呢?从背包容量为0开始,1号物品先试,0,1,2,的容量都不能放.所以置0,背包容量为3则里面放4.这样,这一排背包容量为4,5,6,....10的时候，最佳方案都是放4.假如1号物品放入背包.则再看2号物品.当背包容量为3的时候，最佳方案还是上一排的最价方案c为4.而背包容量为5的时候，则最佳方案为自己的重量5.背包容量为7的时候，很显然是5加上一个值了。加谁??很显然是7-4=3的时候.上一排 c3的最佳方案是4.所以。总的最佳方案是5+4为9.这样.一排一排推下去。最右下放的数据就是最大的价值了。(注意第3排的背包容量为7的时候,最佳方案不是本身的6.而是上一排的9.说明这时候3号物品没有被选.选的是1,2号物品.所以得9.)
从以上最大价值的构造过程中可以看出。
f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}这就是书本上写的动态规划方程.这回清楚了吗?
下面是一个简单的程序代码（本代码为了容易理解，没有做任何优化，敬请谅解）:
//
// main.cpp
// TestC++06
//
// Created by fei dou on 12-8-11.
// Copyright (c) 2012年 vrlab. All rights reserved.
//
#include <iostream>
#include <vector>
#include <algorithm>
#define N 3
using namespace std;
const int W[] = {3, 4, 5};
const int P[] = {4, 5, 6};
void zeroOnePake(const int objNum, const int volumOfPack, const int* W, const int* P, vector<int> &result, int &maxValue);
void zeroOnePake(const int objNum, const int volumOfPack, const int* W, const int* P, vector<int> &result, int &maxValue)
{
int **c = new int*[objNum + 1];//动态生成二维数组，用来保存价值，这里大小加一是为了保存零个物体和容量为零的初始情况，辅助计算
for (int i =0; i <= objNum; ++ i)
c[i] = new int[volumOfPack + 1];
bool **d = new bool*[objNum + 1]; //用来记录选择了哪些物体
for (int i = 0; i <= objNum; ++ i)
{
d[i] = new bool[volumOfPack + 1];
memset((void*)d[i], false,sizeof(d[i])); //初始化为0
}
//初始化c
for(int i =0; i <= volumOfPack; ++i)
c[0][i] = 0;//没有物体的时候价值都是零
//动态规划求解
for (int i =1; i <= objNum; ++i)
{
for (int j =0; j <= volumOfPack; ++j)
{
int tempC = 0;
if (j - W[i] >= 0)
{
tempC = c[i - 1][j - W[i]] + P[i - 1];
d[i][j] = true;//表示选择了i物体
}
c[i][j] = max(c[i-1][j], tempC);
}
}
//存储最大价值
maxValue = c[objNum][volumOfPack];
//回溯找到选择的物体
int i = objNum;
int j = volumOfPack;
while (i >= 1)
{
if (d[i][j] == true)
{
result.push_back(i);
-- i;
j -= W[i];
}
else
-- i;
}
reverse(result.begin(), result.end());//翻转,转换成正确顺序的物体序列
//释放空间
for (int i =0; i <= objNum; ++i)
delete[] c[i];
delete[] c;
for (int i =0; i <= objNum; ++ i)
delete[] d[i];
delete[] d;
}
int main (int argc, const char * argv[])
{
vector<int> result;
int maxValue;
zeroOnePake(N, 10, W, P, result, maxValue);
cout << "计算的结果是：" << maxValue << endl;
cout << "入选的物体有：" << endl;
for (int i =0; i < result.size(); ++ i )
cout << result[i] << " ";
cout <<endl;
return 0;
}
程序运行结果是：
计算的结果是：11
入选的物体有：
2 3