网站建设与管理维护 大学论文,wordpress头像 换多说,网站开发需要哪些技能,全国中小企业融资综合示范平台动态规划
-动态规划方法方法代表了这一类问题#xff08;最优子结构or子问题最优性#xff09;的有一半解法#xff0c;是设计方法或者策略#xff0c;不是具体算法
-本质是递推#xff0c;核心是找到状态转移的方式#xff0c;写出dp方程
-形式:记忆性递归递推01背包问题…动态规划
-动态规划方法方法代表了这一类问题最优子结构or子问题最优性的有一半解法是设计方法或者策略不是具体算法
-本质是递推核心是找到状态转移的方式写出dp方程
-形式:记忆性递归递推01背包问题 有n个重量和价值分别为wivi的物品从这些物品中挑选出总重量不超过n的物品求所有挑选方案中的值总和的最大值
1n1002
1wi,vi100
1w10000输入、n4(w,v){(2,3),(1,2),(3,4),(2,2)}w5
输出7{选择第013号物品}因为对每个物品只有选和不选两种情况所以这个问题称为01背包public class Case_01背包问题{static int[] w{2,1,3,2};//重量表static int[] v{3,2,4,2};//价值表static int n4;//物品数量static int W5;//背包的承重极限public static void main(String[] args){int wwW;int ansdfs(0,ww);System.out.println(ans);}static int dfs(int i,int ww){if(w0)return 0;//装不进去if(in)return 0;//每东西可选了int v2dfs(i1,ww);//不选择当前物品if(www[i]){int v1v[i]dfs(i1,ww-w[i]);//选择当前物品return max(v1,v2);;}else{return v2;}}
static int[][] rec;
}重叠求解记忆性递归
重叠子问题不重复求解public static void main(String[] args){int wwW;int ansdfs(0,ww);System.out.println(ans);recnew int[n][w1];for(int i0;in;i){Arrays.fill(rec[i],-1);//每一行都填充为-1}ansm(m,v,0,n,W);System.out.println(ans);}static int m(int i,int ww){mif(w0)return 0;//装不进去if(in)return 0;//每东西可选了//计算之前做查询if(rec[i][ww]0){return rec[i][ww];}int v2m(i1,ww);//不选择当前物品if(www[i]){int v1v[i]m(i1,ww-w[i]);//选择当前物品ansmax(v1,v2);;}else{ansv2;}//计算之后做保存rec[i][ww]ans;return ans;}01背包问题dpdynamic programming
(w,v) 0 1 2 3 4 5
(2,3) 0 0 3 3 3 3
(1,2) 0 2 要20不要3 5要23不要3 5要23不要3 5要23不要3
(3,4) 0 2 3 540,5 642,5 7435
(2,2) 0 2 3 5 6 7定义从小到大的背包初始化第一行然后根据第一行去推其他行
看当前背包是否能装下给这个物品若是装不下则取上一行相同容量背包的最大价值为当前这个背包的价值
若是能装下则要比较两种情况选与不选若选择这个物品这加上这个物品的价值背包则减去这个物品的容量
剩余的容量肯定比之前小则在上一行找剩余容量的最大价值两者相加即为选择这个物品的最大价值若是不选
则取上一行的最大价值为当前最大价值比较选与不选两者的最大值取最大值作为当前背包的最大价值
当dp到最后右下角即为答案static int dp(){int[][] dpnew int[n][w1];//初始化dp表的第一行for(int i0;iW1;i){if(iw[0]){//每种容量0号的物体dp[0][i]v[0];}else{dp[0][i]0;}}//其他行for(int i1;in;i){for(int j0;jW1;j){if(jw[i]){//要的起int i1v[i]dp[i-1][j-w[i]];//选择当前物品int i2dp[i-1][j];//不选dp[i][j]max(i1,i2);}else{dp[i][j]dp[i-1][j];}}}return dp[n-1][W];} 钢条分割 Serling公司购买长钢条将其切割为短钢条出售,切割工序本身没有成本支出公司管理层希望知道最佳的切割方案
假定我们知道Serling公司出售一段长为i英寸的的钢条价格为pi(i1,2,...单位为美元)钢条长度均为整英寸| 长度i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| - | - | - | - | - | - | - | - | - | - |
价格pi | 1 | 5 | 8 | 16 | 10 | 17 | 17 | 20 | 24 | 30 |钢条切割问题是这样的给定一段长度为n英寸的钢条和一个价格表pi(i1,2...n),求切割钢条方案使得售价收益rn最大
注意如果长度为n英寸的钢条的价值pn足够大最优解可能就是完全不需要切割递归-记忆性递归-dppublic class Case_钢条切割{//有重复子问题static int r(int x){if(x0){return 0;}int ans0;for(int i1;ix;i){//取不同种切法的最大值int vp[i-1]r(x-i);//p[i-1即]从不切开始ansmax(v,ans);}return ans;}static int[] vsnew int[n1];static int r1(int x){if(x0){return 0;}int ans0;for(int i1;ix;i){//取不同种切法的最大值if(vs[x-i]-1)vs[x-i]r1(x-i);int vp[i-1]vs[x-i];//p[i-1]为这么长的钢材不切割时的价钱从不切开始ansmax(v,ans);}vs[x]ans;return ans;}static int dp(){vs[0]0;for(int i1;in;i){//拥有钢条长度for(int j1;ji;j){vs[i]max(p[j]vs[i-j],vs[i]);}}return vs[n];}} 数字三角形 在数字三角形中寻找一条从顶部到底边的路径使得路径上所经过的数字之和最大
路径上的每一步都只能网左下或右下走。只需要求出这个最大和即可不必给出具体路径。
三角形的行数大于1小于等于100数字为0~9
输入格式:
5//表示三角形的行数。接下来输入三角形73 88 1 02 7 4 44 5 2 6 5
要求输出最大和dfs
public static int maxSumUsingRecursive(int[][] triangle,int i,int j){int rowIndextriangle.length;if(irowIndex-1){return triangle[i][j];}else{//顶点的值max(左侧支线的最大值右侧支路的最大值)return triangle[i][j]Math.max(maxSumUsingRecursive(triangle,i1,j),maxSumUsingRecursive(triangle,i1,j1));}}dp递推
打表法public static int maxSumUsingDp(int[][],int i,int j){int rowCounttriangle.length;//行数int columnCounttriangle[rowCount-1].length;//最后一行的列数int[][] dpnew int[rowCount][ColumnCount];for(int k0;kcolumnCount;k){dp[rowCount-1][k]trianle[rowCount-1][k]//初始化最后一行}for(int krowCount-2;k0;k--){for(int l0;lk;l){dp[k][l]triangle[k][l]max(dp[k1][l1])}}return dp[0][0];}可以用滚动数组来表示底下一层求完就没用了,可以覆盖掉public static int maxSumUsingDp(int[][],int i,int j){int rowCounttriangle.length;//行数int columnCounttriangle[rowCount-1].length;//最后一行的列数int[] dpnew int[ColumnCount];for(int k0;kcolumnCount;k){dp[k]trianle[rowCount-1][k]//初始化最后一行}for(int krowCount-2;k0;k--){for(int l0;lk;l){dp[l]triangle[k][l]max(dp[k1][l1])}}return dp[0][0];} 最长公共子序列 求最大公共子序列
AB34C
A1BC2结果为ABC
更多案例请看测试用例ArrayListCharacterdfs(String s1,String s2){int len1s1.length();int len2s2.length();ArrayListCharacter ansnew ArrayList;for(int i0;ilen1;i){//以i字符开头的公共子序列ArrayListCharacter listnew ArrayList;//和s2的每个字符【【比较for(int j0;jlen2;j){if(s1.charAt(i)s2.charAt(j)){//如果相同list.add(A1.charAt(i));list.addAll(dfs(s1.substring(i1),s2.substring(j1)));break;}}if(list.size()ans.size()){//以不同字符开头公共序列求最长anslist;}}}dpB A 3 4 C s1
A 0 1 1 1 1
1 0 1 1 1 1
B 1 1 1 1 1
C 1 1 1 1 2
2 1 1 1 1 2
s2
当找到相同的字符,每个位置都找左、上、和左上角1的最大值若没有找到相同字符则找左、上 的最大值
String solution(String s1,String s2){int len1s1.length();int len2s2.length();int[][] dpnew int[len11][len21];//动规数组int flag0;//初始化第一行for(int i1;ilen1;i){if(flag1){dp[i][1]1;}else if(s1.charAt(i-1)s2.charAt(0){dp[i][1]1;flag1;}else{dp[i][1]0;}}for(int i2;ilen1;i){//Mfor(int j2;jlen2;j){int maxOfleftAndUpMath.max(dp[i-1][j],dp[i][j-1]);if(s1.charAt(i-1)s2.charAt(j-1)){//从1开始的数组所以要i-1dp[i][j]Math.max(maxOfleftAndUp,dp[i-1][j-1]1);}else{dp[i][j]maxOfLeftAndUp;}}}return parseDp(dp,s1,s2);}//还原子最长子序列
private String parseDp(int[][] dp,String s1,String s2){int Ms1.length();int Ns2.length();StringBuilder sbnew StringBuilder();while(M0N0){//比左和上大一定是当前位置的字符相等if(dp[M][N]Math.max(dp[M-1][N],dp[M][N-1])){sb.insert(0,s1.charAt(M-1));M--;N--;}else{//一定选择的是左边和上边的大者if(dp[M-1][N]dp[M][N-1]){M--;//往上移}else{N--;//往左移}}}return sb.toString();
}dp状态转移方程
用已知来推未知 完全背包问题 有n个重量和价值分别为wivi的物品从这些物品中挑选出总重量不超过w的物品求所有挑选方案中的价值总和的最大值(w,v){(2,3),(1,2),(3,4),(2,2)}0 1 2 3 4 5 6 7 8 9 10
(2,3) 0 0 3 3 6 6 9 9 12 12 15
(1,2) 0 2 22 24......
(3,4) 0 2 4 6
(2,2)两个核心式子:
拿一个后剩余容量找当前行和上一行的最大值一个不拿找上一行该列的值比较拿与不拿的最大值
该行前面就包含了不选的情况当容量不足时取上一行该容量的价值
因为需要选的物品重量价值不同会出现当前行的该容量的价值比上一行的价值要大的情况
dp[i][j]Math.max(v[i]dp[i][ww-w[i]],dp[i-1][j])
上一行的该列意味着旧的该容量价值的最大值新的该容量的价值与旧的取最大值
因此上面求出来的dp还要和上一行dp比较一下
dp[i][j]Math.max(dp[i][j],d[i-1][j]) 最长递增子序列 输入4 2 3 1 5 6
输出3因为 2 3 5 组成了最长递增子序列
public class Case_最长递增子序列{public static void main(String[] args){int[] arr{4,2,3,1,5};System.out.println(f(arr));}private static int f(int[] arr){for(int i0;iarr.length;i){int pi;int cnt0;for(int ji1;jarr.length;j){if(arr[j]arr[p]){cnt;pj;}}if(cntmaxCnt){maxCntcnt;}}//maxCntmax(maxCnt,cnt);}return maxCnt;}dp
4 2 3 1 5 6
1 1 2 1 3 4并不是说最后一个就是最大递增子序列
把每位求出来最后再整体作一个maxstatic int[] dpnew int[arr.length];
private static int dp(int[] arr){dp[0]1;//初始化第一位为1for(int i0;iarr.length;i){//每个位置cnt1;for(int ji-1;j0;j--){//向前找比当前位置小的if(arr[i]arr[j]){cntmax(dp[j]1,cnt);}}dp[i]cnt;}int ans-1;for(int i0;isb.length;i){ansmax(ans,dp[i]);}return ans;
}dp[i]
长度为i最长递增子序列LIS最末尾的数避免陷入思维定势
初始化第一个元素遍历剩余的元素若是比最后一个dp元素大则添加到其后面若是比它小则放在dp数组第一个大于arr的元素位置上4 2 3 1 5 6 4 8 5 9
4[1]
2[1] 3[2]
1[1] 3[2]
1[1] 3[2] 5[3]
1[1] 3[2] 5[3] 6[4]
1[1] 3[2] 4[3] 5[4] 8[5] 9[6]结果为6private static int dp1(int[] arr){dpnew int[arr.length];dp[1]arr[0];//长度为1的最长递增子序列初始化为第一个元素int p1;//记录dp更新的最后位置for(int i1;iarr.length;i){if(arr[i]dp[p]){dp[p1]arr[i];p;}else{//扫描dp数组替换第一个比arr大的//可以用二分法优化查找for(int j0;j0;j){if(dp[i]arr[i]){dp[i]arr[i];break;}}}}return 0;
}小结
动态规划用于解决多阶段决策最优化问题
三要素:
-阶段
-状态
-决策
两个条件:
-最优子结构(最优化原理)
-无后效性:当前状态是前面状态的完美总结是否可以用动态规划否则用搜索
-模型匹配:多做题掌握经典模型一维:上升子序列模型背包波形二维:最长公共子序列问题
-寻找规律:规模由小到大或者由大到小做逐步分许
-放宽条件或增加条件
一般过程-找到过程演变中变化的量状态以及变化的规律状态转移方程-确定一些初始状态通常需要dp数组来保存-利用状态转移方程退出最终答案
解法-自顶向下递归:如果有重叠子问题带备忘录-自底向上递推贪心和动规可以用局部最优解来推导全局最优解,即动态规划贪心:这一阶段的解由上一阶段直接推导出动规:当前问题的最优解不能从上一阶段子问题简单得出需要前面多杰阶段多层子问题共同计算出因此需要保留历史上求解过的子问题及其最优解
