哪里有网站建设哪家好谷歌搜索引擎363入口

当前位置： 首页 > news >正文

哪里有网站建设哪家好,谷歌搜索引擎363入口,适合设计制作公司的网站asp远吗,湛江模板建站多少钱目录 一、0-1背包 1、概述 2、暴力枚举法 3、动态规划 二、石子合并问题 1、概述 2、动态规划 3、环形石子怎么办#xff1f; 三、数字三角形问题 1、概述 2、递归 3、线性规划 四、租用游艇问题 一、0-1背包 1、概述 0-1背包#xff1a;给定多种物品和一个固定…目录 一、0-1背包 1、概述 2、暴力枚举法 3、动态规划 二、石子合并问题 1、概述 2、动态规划 3、环形石子怎么办 三、数字三角形问题 1、概述 2、递归 3、线性规划 四、租用游艇问题  一、0-1背包 1、概述 0-1背包给定多种物品和一个固定重量W的背包每种物品有一个固定的重量价值现在要将物品装入背包每种物品至多装入一个使总重量不超过W且总价值最大。 约束条件和优化目标如下 2、暴力枚举法 暴力枚举法也是使用递归的方式假设对前i个物品分析总重量为c当前总价值为P。那么存在递归条件 另外当重量小于0时总价值为-∞代码中可以用-999替代物品个数小于等于0总价值为0。 暴力枚举法依赖递归方式没有减少子问题个数所以根据递归树计算复杂度为。 伪代码如下 代码实例  //暴力枚举public static int violate_knapsack(int weight,int i,int weights[],int values[]){if (weight0){return -9999; }if (i0) { return 0;}int p1violate_knapsack(weight-weights[i],i-1,weights,values); //选中i物品int p2violate_knapsack(weight,i-1,weights,values); //不选i物品int pp1values[i]p2?p1values[i]:p2; return p;} 3、动态规划 动态规划方法通过建立备忘录的方式前i个物品总重量为j的时刻永远依赖于前面的子结构。M数组为加入前i个物品后总重量为j时的总价值Rec数组表示是否有物品添加若添加则为1不添加则为0。 原理 参数count代表总类别个数weight代表背包重量weights为物品重量values为物品价值name为物品名称。 1首先M数组0行0列均为初值0注意行为重量列为种类个数。 2按每行逐个值来填写M和Rec。如前i个物品总重量为j的情况下即求M[i][j]时如果该物品重量小于背包重量且在前i-1个物品总重量为j-当前物品重量时的总重量当前物品价值的总价值大于前i-1个物品总重量为j时的总价值时M填写较大的总价值Rec1。条件写为 3由于调用j-当前物品重量时有可能为负数所以保证最小值为0设为minor。 4如果不满足2条件则M[i][j]填上一行同列的M[i-1][j]值即不选这个物品索引为i-1的总价值。Rec为0。 5最优解追寻Rec数组倒序查找i取最大值逐次减1判断条件如果Rec数组为1则从总重量weight中减少weights[i-1]输出name[i-1]物品直到i取1。 //0-1背包问题 import java.util.ArrayList; public class backage {public static void main(String []args){int values[]{24,2,9,10,9};int weights[]{10,3,4,5,4};int count5;int weight13;int M[][]new int [count1][weight1];int Rec[][]new int [count1][weight1];String name[]{beer,cocacola,cookie,bread,milk};//暴力求解System.out.println(violate_knapsack(weight,count-1,weights,values)); //建立M数组Rec数组 knapsack(count,weight,M,Rec,weights,values);//M数组for(int i0;icount1;i){for(int j0;jweight1;j){System.out.print(M[i][j]\t);}System.out.println();}//Rec数组for(int i0;icount1;i){for(int j0;jweight1;j){System.out.print(Rec[i][j]\t);}System.out.println();}//输出最优解Print(count,weight,Rec,name,weights);} //动态规划public static void knapsack(int count,int weight,int M[][],int Rec[][],int weights[],int values[]){for(int i0;icount1;i) //0行0列没有值参与M[i][0]0;for(int j0;jweight1;j)M[0][j]0;for(int i1;icount1;i) //第一行的表示加入第一个物品但是第一个物品在索引0处{for(int j1;jweight1;j){int minor; //minor的设计是防止j-weights出现小于0有可能背包重量小于上一行物品的重量从而小于背包质量小于背包质量默认为0if(j-weights[i-1]0)minor0;elseminorj-weights[i-1];if((weights[i-1]j) (values[i-1]M[i-1][minor]M[i-1][j])) //如果可以替换,M替换为新值Rec更新为1{M[i][j]values[i-1]M[i-1][minor];Rec[i][j]1;}else{M[i][j]M[i-1][j]; //不能修改时M用上一行同列值替换Rec更新为0Rec[i][j]0;}}}}//输出最优解public static void Print(int count,int weight,int Rec[][],String name[],int weights[]){for(int icount;i0;i–){if(Rec[i][weight]1){System.out.println(name[i-1]);weightweight-weights[i-1];}}} M数组和Rec数组的写法 二、石子合并问题 1、概述 现在有n堆石子排成一排要求将石子有次序地合并成一堆规定每次只能选相邻的两堆石子合并成新的一堆并将新的一堆石子数记为该次合并的得分设计一个算法将n堆石子合并成一堆的最小得分和最大得分。 类比矩阵连乘问题求解利用动态规划设计m和s数组最大值为m[1][n]。 2、动态规划 动态规划转移方程最小值 动态规划转移方程最大值 3、环形石子怎么办 如果题目要求石子堆围成一圈其他要求不变我们可以考虑将数组变为一个重复数组由环形变为线性。如{1,2,3}则变为{1,2,3,1,2,3}n2*n然后考虑(j-i)arrlength时才满足原来的最多三个石子堆合并的问题。 动态规划转移方程相同只是多了一个退出循环的条件同样的生成m数组假设石子堆为{4,4,5,9}当前生成最小值m数组应该为下图示例 可以看到原先的m[1][n]为最小值现在应该讨论也就是四个数的最小值。 代码示例 //石子合并问题 public class stonemerge {public static void main(String[] args){int arr[]{4,4,5,9};int narr.length;int m[][]new int[n1][n1]; int m[][]new int[n*21][n*21];int s[][]new int[n1][n1]; minserge(arr,m);System.out.println(trackmin(arr, m));maxserge(arr, m);System.out.println(trackmax(arr,m));}//最小合并m数组 public static void minserge(int arr[],int m[][]){int narr.length*2;int arr[]new int[n];addarr(arr,arr);for(int i1;in;i)m[i][i]0;for (int r 2; r n; r) {for (int i 1; i n - r 1; i) { int j i r - 1;if((j-i)arr.length)break; m[i][j] m[i 1][j] sum(i,j,arr); for (int k i 1; k j; k){int t m[i][k] m[k 1][j] sum(i,j,arr);if (t m[i][j]) m[i][j] t;}}}}//最大合并m数组public static void maxserge(int arr[],int m[][]){int narr_.length*2;int arr[]new int[n];addarr(arr,arr);for(int i1;in;i)m[i][i]0;for (int r 2; r n; r) {for (int i 1; i n - r 1; i) { int j i r - 1;if((j-i)arr_.length)break; m[i][j] m[i 1][j] sum(i,j,arr); for (int k i 1; k j; k){int t m[i][k] m[k 1][j] sum(i,j,arr);if (t m[i][j]) m[i][j] t;}}}}//合并代价public static int sum(int i,int j, int arr[]){int tot0;for(int mi-1;mj-1;m)totarr[m];return tot;}//环形转线性数组生成public static void addarr(int arr[],int arr[]){for(int i0;iarr.length;i){if(iarr.length)arr[i]arr[i];elsearr[i]arr[i-arr.length];}}//最小值public static int trackmin(int arr[],int m[][]){int narr.length;int minm[1][n];for(int i2;in;i){if(m[i][ni-1]min)minm[i][ni-1];}return min;}//最大值public static int trackmax(int arr[],int m[][]){int narr.length;int maxm[1][n];for(int i2;in;i){if(m[i][ni-1]max)maxm[i][ni-1];}return max;} } 三、数字三角形问题 1、概述 给定一个由n行数字组成的数字三角形设计算法计算从三角形的顶至底的一条路径每次必须下降一层使该路径经过数字总和最大如下图路线7-3-8-7-5总和30。 2、递归 递归条件 当xn-1时为最底层数字返回该数字。 //递归方法 public static int test(int x,int y,int nums[][]) {int nnums.length;if(x n-1) {return nums[x][y];}return (nums[x]y);} 3、线性规划 状态转移方程与递归条件一样只不过从倒数第二层向上叠加参数i每层的值改变为当前层到底层的最大值变量k遍历某一层的每个数字计算到底层的最大值并保存。 //动态规划 public static int max(int nums[][]) {for(int inums.length-2;i0;i–){int jnums[i].length;for(int k0;kj;k){nums[i]k;}}return nums[0][0]; } 四、租用游艇问题 游艇出租站租用游艇并在下游的任何一个游艇出租站归还游艇游艇出租站i到游艇出租站j之间的租金为rij1ijn,设计算法计算出游艇出租站1到游艇出租站n的最少租金。 输入的数字第一行代表1到2的距离和1到3的距离第二行代表2到3的距离。 //租用游艇问题 public class rentyacht {public static void main(String [] args){int cost[][]{{5,15},{7}};int ncost.length;System.out.println(rentmin(cost,n));} public static int rentmin(int[][] cost, int n) {int[][] best new int[n 1][n 1];for(int i n - 1; i 1; i–) {best[i][n] cost[i-1][n-1];for(int j n - 1; j i; j–) {best[i][n] cost[i-1][j-1] best[j][n]best[i][n]?cost[i-1][j-1] best[j][n]:best[i][n];}}return best[1][n];} }