李立新动态规划

动 态 规 划例 1、01 背包 问题：有 n 件物品，每个物品有一个重量和一个价值。同时，有一个背包，容量为 wik,要求从 n 物品中任取若干伯，使重量之和wk，而价值之各为最大。例：n=4，w k=38重量：7、12、18、21价值：16、23、35、43列表如下：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 200 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 0 0 0 0 0 0 0 16 16 16 16 16 16 16 16 16 16 16 16 16 162 0 0 0 0 0 0 0 16 16 16 16 16 23 23 23 23 23 23 23 39 393 0 0 0 0 0 0 0 16 16 16 16 16 23 23 23 23 23 23 35 39 394 0 0 0 0 0 0 0 16 16 16 16 16 23 23 23 23 23 23 35 39 3921 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 380 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 016 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 1639 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 3939 39 39 39 51 51 51 51 51 58 58 58 58 58 58 58 74 7443 43 43 43 51 51 51 59 59 59 59 59 66 66 66 66 74 74递推方程： )0(;,1,max;0, iwjiiicwjigjijig 结果保存在 中。,kwn数据结构n , wkw , int c100; w 重量，c 价值int g30500;程序#include#include#define N 4#define M 38int c10100; /*对应每种情况的最大价值*/int knapsack(int m,int n)int i,j,w10 = 0,7,12,18,21,c10 = 0,16,23,35,43;for(i=1;ici-1j) /*如果本物品的价值加上背包剩下的空间能放的物品的价值*/cij=pi+ci-1j-wi; /*大于上一次选择的最佳方案则更新 cij*/else cij=ci-1j;else cij=ci-1j;return(cnm);int main() printf(“%dn“,knapsack(M,N);程序的改进 1，若不用输出方案，可节省空间。程序：#define N 4#define M 38 / 背包容量int g2M+1,w10 = 0,7,12,18,21,c10 = 0,16,23,35,43;for(int i = 0; i g0j-wi+ci) g1j = g0j;else g1j = g0j-wi+ci;for(j = 0; j g1j-wi+ci） ） dog1i=g0j;else g1j=g1j-wi+ci;例 2.字符串变换，设有 2 个字符串，A 串，B 串，今将 B 串变成 A 串，规则如下： 可在任何位置添加字符，添加一个字符称一次变换； 可在任何位置删除字符，删除一个字符称一次变换； 可在任何位置变换字符，变换一个字符称一次变换例 A 串 = abcdefghiB 串 = bcwefgxhi变换过程：1. 在 b 的前面添加a，B 串成为abcwefgxhi ；2. 将w变成d； abcdefgxhi；3. 删除下 。 abcdefghi；共三次变换构造过程，列表如下：a b c d e f g h i0 1 2 3 4 5 6 7 8 90 0 1 2 3 4 5 6 7 8 9b 1 1 1 1 2 3 4 5 6 7 8c 2 2 2 2 1 2 3 4 5 6 7w 3 3 3 3 2 2 3 4 5 6 7e 4 4 4 4 3 3 2 3 4 5 6f 5 5 5 5 4 4 3 2 3 4 5g 6 6 6 6 5 5 4 3 2 3 4x 7 7 7 7 6 6 5 4 3 3 4h 8 8 8 8 7 7 6 5 4 3 4i 9 9 9 9 8 8 7 6 5 4 3方程 1,1,1min; A0,B; ijjigjijg ji ijjig 串 空 ， 全 部 删 除列 ，第 串 空 ， 全 部 添 加行 ，第程序实现#include #include #include int _Min(int a,int b,int c) /求三个最小 int min=a; if (b #define N 6int dN+1 = 0,3,7,6,11,4,5;int fenshu()int gN+1N+1 = 0,cmax;for(int i = 1; i cmax)cmax = dk+1+gik*gk+2i+l;if(cmax #define N 5#define MAX 20int bMAX+1MAX+13 = 13,9,6,11,8,10,9,8,7,16,10,9,10,13,8; /0用来存数，1参与运算，2表示向左(0) ，还是向右(1)int shuta (int n)int i,j;for(i = n-1; i =0; -i) for(j=0; j bi+1j+11) /左边大 bij2 = 0; /选择左边 bij1 = bij0 + bi+1j1; else /右边大 bij2 = 1; /选择右边 bij1 = bij0 + bi+1j+11; return b001;int main() int j = 0;printf(“%dn 路径：“,shuta(N);for(int i = 0; i #include int g2020 = 0,0,13,0,9,6,0,11,8,10,0,9,8,7,16,0,10,9,10,13,8;int b120;#define N 5void qiongju()int b20,s,j,cmax = 0;for(int i = 0; i cmax)cmax = s;for( i = 1; i int p20;int s2020;int m2020;#define N 4#define INF 1e9void MM(int n)int i,k,r,j,t;for(i = 1; i #include #define MAX 50void zixulie(char str1,char str2)int gMAX+1MAX+1;int lg1 = strlen(str1);int lg2 = strlen(str2);for(int j = 0; j gij-1) gij = gi-1j;else gij = gij-1;printf(“%dn“,glg2-1lg1-1);/*i = lg2-1; j = lg1-1;while(gij != 0)if(gij = gi-1j-1+1) printf(“%c “,str2i);i = i-1;j = j-1;else if(gi-1j gij-1) i = i-1;else j = j-1;*/int main()char str1MAX = 0,A,B,C,B,D,A,B;char str2MAX = 0,B,D,C,A,B,A;zixulie(str1,str2);return 0;例 8.最长公共子序列例. str1 = ABCDEFGHIJstr2 = ABDHEJFI#include #include char str120 = 0,A,B,C,D,E,F,G,H,I,J;char str220 = 0,A,B,D,H,E,J,F,I;int g204;void zixulie()int k = 0,j;int lg1 = strlen(str1);int lg2 = strlen(str2);for(int i = 1; i 0; i-)int l = 0,h = 0;for(j = i+1; j gi