动态规划学习

动态规划学习——byJetway动态规划简单地说就是，采用分治的策略，把求最优问题分解为若干个子问题的最优解，子问题也递归地分解为子问题的组合，通过递推递归等方法，把原问题最优解与局部子问题最优解联系起来，以求最后的解。这些局部子问题之间可能有重叠，就是某个子问题可能需要求解多次，因此需要将子问题及其解记录下来，这样对每个子问题只需求解一次。一个简单的问题：一个楼梯有20级，每次走1级或2级，从底走到顶有几种走法？利用递归可以写成：#includeiostreamusingnamespacestd;intf(intn){if(n==0||n==1)return1;elsereturnf(n-1)+f(n-2);}voidmain(){coutf(20)endl;}要注意的是每次递归调用f(n)时都会在内存分配n个新的内存单元。对于其子问题的求解时可能需要求解多次，例如求f(5)时：f(4)f(3)f(2)f(2)f(3)f(1)f(1)f(1)f(5)f(2)f(0)f(0)f(1)f(0)f(1)故当问题符合以下条件时，可以考虑利用动态规划法，把子问题及其解记录下来，这样每个子问题只需求一次：1、对于子问题可以递归地求解；2、这些子问题是有重叠的。所以以上求f（20）的问题可以求解如下：————————递归结构——————？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？#includeiostreamusingnamespacestd;intresult[100];//用于保存结果intf(intn){if(result[n]=0)returnresult[n];intres;if(n==0||n==1)res=1;elseres=f(n-1)+f(n-2);result[n]=res;returnres;}voidmain(){for(inti=0;i=20;i++){result[i]=-1;}coutf(20)endl;}？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？——————递推结构——————#includeiostreamusingnamespacestd;intf[100];voidmain(){f[0]=1;f[1]=1;for(inti=2;i=20;i++){f[i]=f[i-1]+f[i-2];}coutf[20]endl;}？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？动态规划技巧之顺推，顺推的方法就是先计算小的子问题，然后再计算大的子问题，最终把目标问题解决。顺推的方法最关键的一点就是：当求解某个子问题的时候，这个子问题需要用的子问题都必须是已经被求解了的，否则可能有误。例1，一个城市的街道布局如下图（11行，11列），从最左下方走到最右上方，每次只能往上或往右走，一共有多少种走法？利用递推求解如下：？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？#includeiostreamusingnamespacestd;intf[100][100];voidmain(){inti,j;for(i=0;i=10;i++)//初始化{f[i][0]=1;f[0][i]=1;}for(i=1;i=10;i++)//用递推法求解{for(j=1;j=10;j++){f[i][j]=f[i-1][j]+f[i][j-1];}}coutf[10][10]endl;}？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？例2，某某去旅游需要带上一些物品，有5种物品供选择，每种物品的体积、重量、数量、价值分别如下：物品编号体积重量数量价值130310425081053102102423583513020511现在限制总的体积最多为500，总的重量最多为100，请问他最多能带物品的价值为？定义子问题如下：在n种物品里选择，满足总体积x和总重量y的条件下，总价值最多是记为f(n,x,y)，于是原问题就是求解f(5,500,100)。当求f(n,x,y)时，可以先考虑第n个物品的选择，假设它被选用i个，那么前面它的体积为i*v[n]，总重量为i*w[n]，于是前n-1个物品的总体积为x-i*v[n]，总重量为y-i*w[n]，于是f(n,x,y)归约为f(n-1,x-i*v[n],y-i*w[n])。递推程序如下：？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？#includeiostream#includestringusingnamespacestd;intnum,maxx,maxy;intv[6],w[6],c[6],t[6];intf[6][501][101];//用于保存f(n,x,y)voidmain(){inti;//输入参数cinnum;for(i=1;i=num;i++){cinv[i]w[i]c[i]t[i];}cinmaxxmaxy;memset(f,0,sizeof(f));//设置初始解intn,x,y;for(n=1;n=num;n++){for(x=1;x=maxx;x++){for(y=1;y=maxy;y++){intmaxi=c[n];if(x/v[n]maxi)maxi=x/v[n];if(y/w[n]maxi)maxi=y/w[n];for(i=0;i=maxi;i++){if(f[n-1][x-i*v[n]][y-i*w[n]]+i*t[n]f[n][x][y]){f[n][x][y]=f[n-1][x-i*v[n]][y-i*w[n]]+i*t[n];}}}}}intans=0;for(x=0;x=maxx;x++)for(y=0;y=maxy;y++){if(f[num][x][y]ans)ans=f[num][x][y];}coutansendl;}？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？动态规划技巧之递归实现，动态规划多具有递归的结构，所以用递归的方法来实现动态规划往往更直接。这个方法简单来说就是增加一些内存单元来保存子问题的解，在递归求解的开始判断该字问题是否已经被求解过，若是，则直接返回之前记录下来的解，否则递归的求解，并在最后保存这个解，使得以后不用再求相同的问题。如上面背包问题可以实现如下：？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？#includeiostream#includestringusingnamespacestd;intnum,maxx,maxy;intv[6],w[6],c[6],t[6];intf[6][501][101];//用于保存f(n,x,y)intgetf(intn,intx,inty){if(f[n][x][y]=0)returnf[n][x][y];//判断是否被求结果，若是返回if(n==0||x==0||y==0)f[n][x][y]=0;else{intmaxi=c[n];if(x/v[n]maxi)maxi=x/v[n];if(y/w[n]maxi)maxi=y/w[n];for(i=0;i=maxi;i++){if(f[n-1][x-i*v[n]][y-i*w[n]]+i*t[n]f[n][x][y]){f[n][x][y]=f[n-1][x-i*v[n]][y-i*w[n]]+i*t[n];}}}returnf[n][x][y];}voidmain(){inti;cinnum;for(i=1;i=num;i++){cinv[i]w[i]c[i]t[i];}cinmaxxmaxy;memset(f,0xff,sizeof(f));//设置初始解，全部置为负数，表示没被求解过intans=0,x,y;for(x=0;x=maxx;x++)for(y=0;y=maxy;y++)if(getf(num,x,y)ans)ans=getf(num,x,y);coutansendl;}？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？动态规划技巧之子问题编码，有时候子问题比较复杂，不容易直接记录其解，可以考虑把子问题编号，然后把结果保存到一个数组里，即把第i个子问题的解记录在数组的第i个成员里。这个方法的关键是就是设计出一个函数把所有状态一对一的映射到前面的子问题的编号中。最大公共子串问题。从一个给定的串中删去（不一定连续地删去）0个或0个以上的字符，剩下的字符按原来顺序组成的串是该串的子串，例如：“”,“a”,“xb”,“aaa”,“bbb”,“xabb”,“xaaabbb”都是串“xaaabbb”的子串。编程求N个非空串的最长公共子串的长度，2=N=100，N个串中的字符只会是数字0,1，„„，9或是小写字母a，b，„„，z；每个串非空且最多含100个字符；N个串的长度的乘积不超过30000。输入格式：文件第1行是一个整数T，表示测试数据的个数（1=T=10）。接下来有T个组测试数据。各组测试数据的第一行是一个整数Ni，表示第i组数据中串的个数。各组测试数据的第2到N+1行中，每行一个串，串中不会有空格，但行首和行末可能有空格，这个空格当然不算做串的一部分。暂设输入文件为maxsubin.txt输出格式：输出T行，每行一个数，第i行的数表示第i组测试数据中Ni个非空串的最长公共子串的长度。输出文件为maxsubout.txt分析：1、状态表示为F(x1,x2,…,xn)，即第i个串的前xi个字符所组成的子串（i=1,2，…,N）的子串集合最长公共子串的长度。2、构造状态转移方程如果存在xi=0，则F(x1,x2,…,xn)=0如果对每个串，第xi个字符都相等，则F(x1,x2,…,xn)=F(x1-1,x2-1,…,xn-1)+1否则，F(x1,x2,…,xn)=max{F(x1-1,x2,…,xn),F(x1,x2-1,…,xn)…,F(x1,x2,…,xn-1)}3、状态的记录：由于维数不确定，所以不能直接用多维数组记录各个状态的值，可以把各个状态影射到一维数组的前面若干项。具体的说，可以把状态F(x1,x2,…,xn)记录到ARRAY[0…30000]的元素ARRAY[(X1-1)+(X2-1)*LEN1+…+(X3-1)*LEN1*LEN2*…*LENn-1]程序如下：？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？#includefstream#includestringusingnamespacestd;ifstreamfilein(maxsub.in);ofstreamfileout(maxsub.out);charans[30000];charstrin[101][102];intlen[101];intget(intn,int*x){inti,ret,index;for(i=1;i=n;i++){if(x[i]==0){return0;}}for(i=n-1,index=x[n]-1;i=1;i--){index=index*len[i]+x[i]-1;}if(ans[index]=0){returnans[index];}for(i=2;i=n;i++){if(strin[1][x[1]-1]!=strin[i][x[i]-1]){break;}}if(in){intj;for(j=1;j=n;j++)x[j]--;ret=get(n,x)+1;for(j=1;j=n;j++)x[j]++;}else{ret=0;for(i=1;i=n;i++){x[i]--;intrem=get(n,x);if(remret)ret=rem;x[i]++;}}ans[index]=ret;returnret;}voidmain(