手机上怎么做钓鱼网站wordpress前段编辑器

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

手机上怎么做钓鱼网站,wordpress前段编辑器,网站框架有哪些,网站打开慢系列文章目录 目录 系列文章目录动态规划#xff1a;01背包理论基础①二维数组②一维数组#xff08;滚动数组#xff09; 416. 分割等和子集①回溯法#xff08;超时#xff09;②动态规划#xff08;01背包#xff09;未剪枝版剪枝版 动态规划#xff1a;01背包理论基…系列文章目录 目录 系列文章目录动态规划01背包理论基础①二维数组②一维数组滚动数组 416. 分割等和子集①回溯法超时②动态规划01背包未剪枝版剪枝版 动态规划01背包理论基础 (1)输入读取方法 Scanner sc new Scanner(System.in);String str sc.nextLine();int m Integer.parseInt(str.split( )[0]);int n Integer.parseInt(str.split( )[1]);//将String[]数组通过stream流转换成int[]数组int[] weights Arrays.stream(sc.nextLine().split( )).mapToInt(/s-Integer.parseInt(s)/Integer::parseInt).toArray();int[] values Arrays.stream(sc.nextLine().split( )).mapToInt(new ToIntFunctionString() {Overridepublic int applyAsInt(String value) {return Integer.parseInt(value);}}).toArray();Scanner sc new Scanner(System.in);// 读取背包容量和物品数量int m sc.nextInt();int n sc.nextInt();sc.nextLine(); // 消耗掉输入缓冲区的换行符// 读取物品重量和价值int[] weights Arrays.stream(sc.nextLine().split( )).mapToInt(Integer::parseInt).toArray();int[] values Arrays.stream(sc.nextLine().split( )).mapToInt(Integer::parseInt).toArray();// 获取输入数据Scanner sc new Scanner(System.in);int m sc.nextInt();int n sc.nextInt();int[] weights new int[m];for (int i 0; i m; i){weights[i] sc.nextInt();}int[] values new int[m];for (int i 0; i m; i){values[i] sc.nextInt();}①二维数组 1确定dp数组及其含义 表示从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。 2确定递推关系 容量不够一定放不下直接返回不放 i 的最大价值。容量够根据两种方案的价值做选择选价值大的。 不放i相当于在 0 ~ (i-1) 件物品中选择容量不变放i在确定放 i 的前提下腾出空间给 i 获取背包能产生的最大价值再加上 i 的价值。
3考虑初始化 初始化第一行对应物品0如果背包容量不够则设置为0如果够则设置为values[0] 初始化第一列对应背包容量0则无论是什么物品都放不下不能产生任何价值直接为默认值0即可。 代码如下 import java.util.Arrays; import java.util.Scanner; import java.util.function.ToIntFunction;public class BagProblem {public static void main(String[] args) {Scanner sc new Scanner(System.in);String str sc.nextLine();int m Integer.parseInt(str.split( )[0]);int n Integer.parseInt(str.split( )[1]);//将String[]数组通过stream流转换成int[]数组int[] weights Arrays.stream(sc.nextLine().split( )).mapToInt(/s-Integer.parseInt(s)/Integer::parseInt).toArray();int[] values Arrays.stream(sc.nextLine().split( )).mapToInt(new ToIntFunctionString() {Overridepublic int applyAsInt(String value) {return Integer.parseInt(value);}}).toArray();//确定dp数组下标及含义:dp[i][j] 表示从下标为0-i的物品里任取放到容量为j的背包中价值总和最大为多少int[][] dp new int[m][n1];//需要考虑容量和物品数量为0的情况//dp数组初始化for (int i 0; i m; i) {//列初始化dp[i][0] 0;}for (int j weights[0]; j n; j) {//行初始化dp[0][j] values[0];}//确定遍历顺序先遍历物品再遍历容量或者先遍历容量再遍历背包都行//①先遍历物品再遍历容量for (int i 1; i m; i) {for (int j 1; j n; j) {/*** 当前背包的容量都没有当前物品i大的时候是不放物品i的* 那么前i-1个物品能放下的最大价值就是当前情况的最大价值/if(jweights[i]){dp[i][j] dp[i - 1][j];}else {/** 当前背包的容量可以放下物品i* 那么此时分两种情况* 1、不放物品i* 2、放物品i* 比较这两种情况下哪种背包中物品的最大价值最大*/dp[i][j] Math.max(dp[i - 1][j], dp[i - 1][j - weights[i]] values[i]);}}}System.out.println(dp[m-1][n]);} }②一维数组滚动数组 1确定dp数组及其含义 在一维dp数组中dp[j]表示容量为j的背包所背的物品价值可以最大为dp[j]。 2确定递推关系 容量不够 dp[j] 不放物品i。容量够根据两种方案的价值做选择选价值大的。 不放i dp[j] 相当于在 0 ~ (i-1) 件物品中选择容量不变放idp[j - weight[i]] value[i]在确定放 i 的前提下腾出空间给 i 获取背包能产生的最大价值再加上 i 的价值。
3考虑初始化 dp[0]0因为背包容量为0所背的物品的最大价值就是0。那么dp数组除了下标0的位置初始为0其他下标应该初始化多少呢看一下递归公式dp[j] max(dp[j], dp[j - weight[i]] value[i]); dp数组在推导的时候一定是取价值最大的数如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。 import java.util.Arrays; import java.util.Scanner; public class BagProblem {public static void main(String[] args) {Scanner sc new Scanner(System.in);int m sc.nextInt();int n sc.nextInt();sc.nextLine();//接收换行符int[] weights Arrays.stream(sc.nextLine().split( )).mapToInt(Integer::parseInt).toArray();int[] values Arrays.stream(sc.nextLine().split( )).mapToInt(Integer::parseInt).toArray();//确定dp数组及含义(背包容量为j的背包所能装的最大价值int[] dp new int[n 1];//dp数组初始化dp[0] 0;//当背包容量为0时最大价值也为0for (int i 0; i m; i) {//遍历物品for (int j n; j 0; j–) {//遍历容量倒序遍历if (j weights[i]) {dp[j] dp[j];} else {dp[j] Math.max(dp[j], dp[j - weights[i]] values[i]);}}}System.out.println(dp[n]);} }416. 分割等和子集 ①回溯法超时 import java.util.Arrays;public class SplitEqualSumSubsets {public static void main(String[] args) {int[] nums {3,3,3,4,5};Solution solution new Solution();boolean answer solution.canPartition(nums);System.out.println(answer);} }class Solution {int sum 0;int tempSum 0;public boolean canPartition(int[] nums) {for (int i 0; i nums.length; i) {sum nums[i];}if (sum % 2 ! 0) return false;//如果总和为奇数则无法分割为两个等和子集//对数组从小到大排序Arrays.sort(nums);return backTracking(nums, 0);}public boolean backTracking(int[] nums, int startIndex) {//确定回溯函数的参数及返回值//确定回溯函数终止条件if (tempSum sum / 2) return true;if (tempSum sum / 2) {return false;}//确定单层递归逻辑boolean answer1 false;for (int i startIndex; i nums.length; i) {tempSum nums[i];answer1 backTracking(nums, i 1);if(answer1)return true;// 如果找到一个可行解立即返回不再往下遍历tempSum - nums[i];//回溯}return answer1;} }②动态规划01背包 未剪枝版 class Solution {public boolean canPartition(int[] nums) {int sum 0;for (int i 0; i nums.length; i) {sum nums[i];}//总和为奇数不能平分if (sum % 2 ! 0) return false;//确定dp数组含义容量为j的背包放进0~i任意物品后背的最大重量。int target sum / 2;int[] dp new int[target 1];//dp数组初始化dp[0] 0;for (int i 0; i nums.length; i) {//先遍历物品for (int j target; j 0; j–) {//倒序遍历背包容量if (j nums[i]) {dp[j] dp[j];} else {dp[j] Math.max(dp[j], dp[j - nums[i]] nums[i]);}//System.out.print(dp[j]);}//System.out.println();}return dp[target] target;//如果背包装满了即能找到等和子集} }剪枝版 class Solution {public boolean canPartition(int[] nums) {int sum 0;for (int i 0; i nums.length; i) {sum nums[i];}//总和为奇数不能平分if (sum % 2 ! 0) return false;//确定dp数组含义容量为j的背包放进0~i任意物品后背的最大重量。int target sum / 2;int[] dp new int[target 1];//dp数组初始化dp[0] 0;for (int i 0; i nums.length; i) {//先遍历物品for (int j target; j 0; j–) {//倒序遍历背包容量if (j nums[i]) {dp[j] dp[j];} else {dp[j] Math.max(dp[j], dp[j - nums[i]] nums[i]);}//System.out.print(dp[j]);}//System.out.println();//剪枝一下每一次完成内层的for-loop立即检查是否dp[target] target优化时间复杂度if (dp[target] target) return true;}return dp[target] target;//如果背包装满了即能找到等和子集} }