东莞网站建设_东莞网页设计】/百度公司官网

动态规划的基本思想：

将一个问题分解为子问题递归求解，且将中间结果保存以避免重复计算。通常用来求最优解，且最优解的局部也是最优的。求解过程产生多个决策序列，下一步总是依赖上一步的结果，自底向上的求解。

动态规划算法可分解成从先到后的4个步骤：

1. 描述一个最优解的结构，寻找子问题，对问题进行划分。

2. 定义状态。往往将和子问题相关的各个变量的一组取值定义为一个状态。某个状态的值就是这个子问题的解（若有k个变量，一般用K维的数组存储各个状态下的解，并可根    据这个数组记录打印求解过程。）。

3. 找出状态转移方程。一般是从一个状态到另一个状态时变量值改变。

4.以“自底向上”的方式计算最优解的值。

5. 从已计算的信息中构建出最优解的路径。(最优解是问题达到最优值的一组解)

其中步骤1~4是动态规划求解问题的基础，如果题目只要求最优解的值，则步骤5可以省略。

背包问题

01背包: 有N件物品和一个重量为M的背包，（每种物品均只有一件），第i件物品的重量是w[i]，价值是p[i]。求解将哪些物品装入背包可使价值总和最大。

完全背包: 有N种物品和一个重量为M的背包，（每种物品都有无限件可用）。第i种物品的重量是w[i]，价值是p[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包重量，且价值总和最大。

多重背包: 有N种物品和一个重量为M的背包，（第i种物品最多有n[i]件可用），每件重量是w[i]，价值是p[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包重量，且价值总和最大。

01背包问题：

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。

用子问题定义状态：即c[i][v]表示前i件物品恰放入一个重量为m的背包（背包最多盛m重的物体）可以获得的最大价值。则其状态转移方程便是：

c[i][m] = max{ c[i-1][m] , c[i-1][m-w[i] ]+p[i] }

这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入重量为m的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为c[i-1][m]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的重量为m-w[i]的背包中”，此时能获得的最大价值就是c[i-1][m-w[i]]再加上通过放入第i件物品获得的价值p[i]。

下面是给出的一个01问题的实现，代码加了很多注释，给出的测试数据为：

n = 3  //3件物品
m = 10 //背包可盛重量为10
w[ ] = {3,4,5} //重量向量

p[ ] = {4,5,6} //价值向量

首先从底向上计算n*m的价值矩阵，其次从顶向下计算最优解。

package com.test;public class Pack01 {public int [][] pack(int n,int m,int w[],int p[]){      重量为m的背包是指盛的重量最多为m//c[i][v]表示前i件物品恰放入一个重量为m的背包可以获得的最大价值    二维数组的第二个下标是重量限制int c[][]= new int[n+1][m+1];for(int i = 0;i<n+1;i++)  	    初始化二维数组的部分值，重量限制为0时，价值为0c[i][0]=0;for(int j = 0;j<m+1;j++)            当放入前0件物品时，价值为0c[0][j]=0;for(int i = 1;i<n+1;i++){for(int j = 1;j<m+1;j++){//当物品为i件，重量为j时（是说重量限制为j），如果第i件的重量(w[i-1])小于重量j时(第i件的重量小于j说明可以放入)，c[i][j]为下列两种情况之一：//(1)物品i不放入背包中，所以c[i][j]为c[i-1][j]的值 。。不放i，有可能剩余的重量不够i，需要将其它物品拿出。//(2)物品i放入背包中，则背包剩余重量为j-w[i-1],所以c[i][j]为c[i-1][j-w[i-1]]的值加上当前物品i的价值if(w[i-1]<=j){	表示可以放进去if(c[i-1][j]<(c[i-1][j-w[i-1]]+p[i-1]))c[i][j] = c[i-1][j-w[i-1]]+p[i-1];elsec[i][j] = c[i-1][j];}else{          没办法，其余的都拿出来也装不下c[i][j] = c[i-1][j];}}}return c;}/*** 逆推法求出最优解*/public int[] printPack(int c[][],int w[],int m,int n){int x[] = new int[n];		状态数组，1表示放入，0表示不放//从最后一个状态记录c[n][m]开始逆推for(int i = n;i>0;i--){//如果c[i][m]大于c[i-1][m]，说明c[i][m]这个最优值中包含了w[i-1](注意这里是i-1，因为c数组长度是n+1)如果c[i][m]大于c[i-1][m]表明在重量限制为m时，放入第i件物品比不放入第i件物品时获得的价值大if(c[i][m]>c[i-1][m]){x[i-1] = 1;		将第i件放入m -= w[i-1];	减小可用重量}}for(int j = 0;j<n;j++){System.out.println(x[j]);}return x;}public static void main(String args[]){int n = 3;				n表示物品的数量int m = 10;				m表示背包能盛的最大重量int w[]={3,4,5};		w[i]指第i+1件物品的重量，三个元素表示一共有3件物品int p[]={4,5,6};		p[i]指第i+1件物品的价值Pack01 pack = new Pack01();int c[][] = pack.pack(n, m, w, p);  有了上述四个变量就可以求出二维矩阵pack.printPack(c, w, m,n);}
}

原文地址：http://blog.csdn.net/fg2006/article/details/6766384