网站建设及维护机,北京网站设计十年乐云seo,黑群辉wordpress,织梦 和wordpress1.背包问题 #xff08;1#xff09;01背包 从n个重量和价值分别为wi,vi的物品#xff0c;从中选出不超过W的物品#xff0c;每种物品仅有一件#xff0c;求所有方案中V的最大值。 最朴素最简单也最费时的方法#xff1a;O(2^n) int rec(int i,int j)//从第i个开始挑选总…1.背包问题 101背包 从n个重量和价值分别为wi,vi的物品从中选出不超过W的物品每种物品仅有一件求所有方案中V的最大值。 最朴素最简单也最费时的方法O(2^n) int rec(int i,int j)//从第i个开始挑选总重小于j的部分 递归 递归终止条件in return 0; 递归分支① jwi resrec(i1,j); //无法挑选看下一个 ② resmax(rec(i1,j),rec(i1,j-w[i])v[i]))//挑选不挑选选其中大的 分析递归搜索深度→n每层两次分支选与不选有重复计算 优化记录每次递归的结果记忆化搜索 Int dp[MAX_N][MAX_N]; 递归 int rec(int i,int j) 初始条件memset(dp,-1,sizeof(dp)); 终止条件①dp[i][j]0 returndp[i][j]//已计算过 ②in return 0; 递归分支① jwi resrec(i1,j); //无法挑选看下一个 ② resmax(rec(i1,j),rec(i1,j-w[i])v[i]))//挑选不挑选选其中大的 分析及remark复杂度O(nW) 数组初始化①memset(type *arrary,figure,sizeof(arrary)) 只能填充0-10x3f3f3f3f其他值不可以 memset按照1字节为单位对内存填充-1的二进制每一位均为1 ②fill(type* arrary,type *arraryn,figure) 可赋值任意值 递归 ↓↓↓↓↓↓ for(int in-1;i0;i--) // 递推(双重循环) for(int j0;jw;j) { if(jw[i]) dp[i][j]dp[i1][j]; //不选 else dp[i][j]max(dp[i1][j],dp[i1][j-w[i]]v[i]);} 其他3种递推写法来源《挑战程序设计竞赛》 2完全背包 递推关系13重循环有重复计算复杂度O(nW^2) For(int i0;in;i) For(int j0;jw;j) For(int k0;k*w[i]j;k) Dp[i1][j]max(dp[i1][j],dp[i1][j-k*w[i]]k*v[i]) 优化(左上→右下 变为 左→右) Dp数组初始化为0 For(int i0;in;i) For(int j0;jw;j) { If(jw[i]) dp[i1][j]dp[i][j]; Else dp[i1][j]max(dp[i][j],dp[i1][j-w[i]]v[i]) } 只有这里与01背包不同前j个已更新过可直接用 进一步优化用一个数组实现只需要记录当前最优状态 比较01背包与完全背包循环方向不同 2.LCS(Longest common subsequence) dp[n][m]即为所求 for(int i0;in;i) for(int j0;jm;j) { if(s[i]t[i]) dp[i1][j1]dp[i][j]1; else dp[i1][j1]max(dp[i1][j],dp[i][j1]) } 3.LIS(Longest Increasing subsequence) dp[i]:以ai为结尾的最长上升子序列长度 dp[i]max{1,dp[i]1|ji且ajai} O(n^2) int res; for(int i0;in;i) { dp[i]1; for(int j0;ji;j) if(a[j]a[i]) //每存在ajaiji,dp[i]更新一次 dp[i]max{dp[i],dp[j]1}; } resmax{dp[i]|0in} Remark: 其他方法 可以用lower_bound(); dp[i]:长度为i1的上升子列中末尾元素的最小值不存在的话为inf dp[max_n]初始化为inf按顺序逐个考虑数列的元素对于每个ai如果i0||dp[i-1]ai,就用dp[i]min(dp[i],ai)更新最终找出使得dp[i]inf的最大的i1即为结果。DP直接实现可以在On^2的时间内给出结果但可以进一步优化dp数组中除inf之外是单调递增的对于每个ai最多有一次更新更新的位置可用二分的方法优化时间复杂度可以降低到Onlogn int dp[max_n] void solve { fill(dp,dpn,inf); for(int i0;in;i) *lower_bound(dp,dpn,a[i])a[i]; reslower_bound(dp,dpn,inf)-dp; } // lower_bound()可以从已排好序的a中利用二分搜索找出满足aik的ai的最小的指针类似的还有upper_bound,找出的为aik的最小指针 //求n个有序数组a中k的个数可以用upper_bound(a,an,k)-lower_bound(a,an,k);转载于:https://www.cnblogs.com/Egoist-/p/7391224.html
