前言

前边我们讲过分治法，分治法的核心是将一个问题分解为n个小问题，最后合并结果。而动态规划算法的核心是穷举法,以及要寻找到一个状态方程，需要用一个DP表或者函数来记录穷举的结果，从穷举过程中选择最优的值，最后得到原始问题的解。

1.0-1背包问题

1.1 基本概念

完全背包问题是背包问题的一种变种，与 0-1 背包问题不同的是，每个物品可以无限次选择放入背包，即可重复使用。动态规划是解决完全背包问题的常用方法。

1.2 具体问题

有n个物品，每个物品的价值为Vi,重量为Wi,背包的容量为C，现在需要将n个物品放入背包，总重量不能超过背包的容量，使得装入的物品的价值达到最大。
求解的问题：放入背包的价值最大
约 束 条 件：重量之和不能超过背包的容量。

实际例子： 假设物品的个数为5个，背包的容量为20，物品的价值和重量如下：

物品编号	1	2	3	4	5
价值v	4	5	10	12	15
重量w	3	4	7	9	12

简单的例子我们可以穷举下：
1.20=4+7+9 此时的价值为: 5+10+12=27
2.19=7+12 此时的价值为：10+15 =25
…等等

1.3 c代码求解

/*** 0-1 背包问题* @param n 物品的个数* @param c 背包的容量* @param w 物品的重量数组* @param v 物品的价值数组* @return dp表*/
int ** KnapsackDp(int n,int c,int *w,int *v,int ** path){int i,tempc;//定义一个二维的数组dp表int ** dp = (int **)malloc(sizeof (int*)*(n+1));for(int i=0;i<=n;i++){dp[i]= (int *)malloc(sizeof (int )*(c+1));}//由于下标是从0开始初始化第一行for(tempc = 0;tempc <= c ;tempc ++){dp[0][tempc]=0;path[0][tempc]=0;}for(i = 1;i <= n ;i ++){dp[i][0]=0;path[i][0]=0;//开始动态for(tempc = 1 ; tempc <= c ; tempc++){path[i][tempc]=0;if( w[i-1] <= tempc){//背包的剩余重量大于物品重量if(v[i-1]+dp[i-1][tempc-w[i-1]] > dp[i-1][tempc]){//放入背包dp[i][tempc]=v[i-1]+dp[i-1][tempc-w[i-1]];path[i][tempc]=1;}else{dp[i][tempc]=dp[i-1][tempc];}}else{dp[i][tempc]=dp[i-1][tempc];}}}return dp;
}

1.4 测试

int main(){int n=5;int c=20;int w[]={3,4,7,9,12};int v[]={4,5,10,12,15};//记录是否放入int ** path = (int **)malloc(sizeof (int*)*(n+1));for(int i=0;i<=n;i++){path[i]= (int *)malloc(sizeof (int )*(c+1));}int **dp = KnapsackDp(n,c,w,v,path);for (int i = 0; i <=n ; ++i) {for (int j = 0; j <= c ; ++j) {printf("%d    ",dp[i][j]);}printf("\n");}for (int i = 0; i <=n ; ++i) {for (int j = 0; j <= c ; ++j) {printf("%d    ",path[i][j]);}printf("\n");}printf("================output==================\n");while ( n >0 && c >0 ){if(path[n][c]==1){c = c-w[n-1];printf("the %d put the package!\n",n);}n--;}
}

2.最长公共子序列

先看一张动态图

代码实现也很简单了