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

贵金属网站建设天津网站建设技术外包

贵金属网站建设,天津网站建设技术外包,如何将模板导入wordpress,深圳哪里做网站好所用代码 java 01背包理论 背包最大重量为:4 重量价值物品0115物品1320物品2430 暴力:O(2^n) 动态规划: 1、二维dp数组 dp[i] [j] dp数组含义:[0, i]物品,任取放进容量为j的背包里的最大价值 递推公式&#xff1a…

所用代码 java

01背包理论

背包最大重量为:4

重量价值
物品0115
物品1320
物品2430

暴力:O(2^n)

动态规划:

1、二维dp数组 dp[i] [j]

  • dp数组含义:[0, i]物品,任取放进容量为j的背包里的最大价值

  • 递推公式:

    • 不放物品i :dp[i-1] [j]
    • 放物品i:dp[i-1] [j - weight[i]] + value[i]

    dp[i] [j] = Math.max(dp[i-1] [j], dp[i-1] [j - weight[i]] + value[i]

  • 初始化:

    dp[i] [j] i:物品 j:背包容量(0 1 2 3 4 )

01234
物品0015151515
物品10n => 由上和左上推出
物品20
  • 遍历顺序:对于二维数组的01背包,先背包后物品,先物品后背包都可以
  • 打印dp数组:

具体代码:

public class 背包01 {public static void main(String[] args) {int[] weight = {1,3,4};int[] value = {15,20,30};int bagSize = 4;bagProblem01(weight,value,bagSize);}public static void bagProblem01(int[] weight, int[] value, int bagSize){int goods = weight.length; // 物品数量int[][] dp = new int[goods][bagSize + 1];// 初始化 - 只有一个物品的时候,不管背包多大,加载都是该物品的价值for (int j = 0; j <= bagSize; j++) {dp[0][j] = value[0];}// 背包i在背包容量为0的时候,最大价值为0for (int i = 0; i < goods; i++) {dp[i][0] = 0;}// 先遍历背包,再遍历物品for (int i = 1; i < goods; i++) {for (int j = 1; j <= bagSize; j++) {if (j < weight[i]){// 当背包容量没有当我物品那么大时,就是放不下物品,最大的重量为i-1时最大重量dp[i][j] = dp[i-1][j];}else {// 可以放下物品时:比较放物品后的价值和没放物品价值谁大dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]);}}}// 打印dp数组for (int i = 0; i < goods; i++) {for (int j = 0; j <= bagSize; j++) {System.out.print(dp[i][j] + "\t");}System.out.println();}}
}
打印结果:
0	15	15	15	15	
0	15	15	20	35	
0	15	15	20	35

2、一维dp数组dp[j] - 滚动数组

  • dp[j]:容量为j的背包最大价值为dp[j] i为物品
  • 递推公式:dp[j] = max(dp[j], dp[j-weight[i]] + value[i])
  • 初始化:dp[0] = 0 其他非负里面的最小值,如0。
  • 遍历顺序:
    • 先遍历物品,再遍历背包
    • 倒序遍历,保证每个物品只被添加了一次。
  • 打印dp数组
public static void bagProblem1(int[] weight, int[] value, int bagSize){int goods = weight.length; // 物品数量int[] dp = new int[bagSize + 1];// 初始化Arrays.fill(dp, 0);// 先遍历背包,再遍历物品for (int i = 0; i < goods; i++) {// j >= weight[i] 保证从右向左遍历的时候dp[j-weight[i]]不会越界for (int j = bagSize; j >= weight[i]; j--){dp[j] = Math.max(dp[j-1], dp[j-weight[i]] + value[i]);}}// 打印for (int MaxValue : dp) {System.out.print(MaxValue + "\t");}
}

分割等和子集 LeetCode 416

题目链接:分割等和子集 LeetCode 416 - 中等

思路

试了滑动窗口,不行。滑动窗口适合连续的数。


应该抽象为一个背包,背包的容量为数组和的一半,只要装下一半,另一半肯定可以。

  • dp[j] :容量为j的背包能装下的最大价值为dp[j]
  • 递推公式:dp[j] = max(dp[j], dp[j-nums[i]] + nums[i]) 重量和价值是相同的
  • 初始化:dp[0] = 0;背包不可能是负数,需初始成非负整数的最大值 0
  • 遍历方向:从右到左
  • 打印dp数组

一维数组:

class Solution {public boolean canPartition(int[] nums) {int sum = 0;for (int num : nums) {sum += num;}if (sum % 2 == 1) return false;// target 相当于背包的容量int target = sum / 2;// dp数组初始为0int[] dp = new int[target + 1];// 物品for (int i = 0; i < nums.length; i++) {for (int j = target; j >= nums[i]; j--){dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]);}}// 看一下最后一个数是不是targetreturn dp[target] == target;}
}

二维数组:

  • dp[i] [j] : 前i个数,其总价值不超过j的最大价值为dp[i] [j] j代表的是背包重量
  • 递推公式:dp[i] [j] = Math.max(dp[i-1] [j], dp[i-1] [j - nums[i]] + nums[i]);
  • 初始化:小于num[0]的不能装,初始化为0,其余为nums[0]
class Solution {public boolean canPartition(int[] nums) {int sum = 0;for (int num : nums) {sum += num;}if (sum % 2 == 1) return false;// target 相当于背包的容量int target = sum / 2;int[][] dp = new int[nums.length][target + 1];// 初始化,只有一个物品时的重量for (int j = 0; j <= target; j++) {dp[0][j] = j > nums[0] ? nums[0] : 0;}// 物品数量for (int i = 1; i < nums.length; i++) {// 背包容量,背包容量0,默认不能装for (int j = 1; j <= target; j++) {// 不能装下物品,最大值就是前一个值if (j < nums[i]){dp[i][j] = dp[i-1][j];}else {dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - nums[i]] + nums[i]);}
//                System.out.print("dp="+dp[i][j] + "\t");}
//            System.out.println();}return dp[nums.length-1][target] == target;}
}

总结

本题主要是分析,只要把该题分析出来是背包问题的话,照着这个思路就非常的简单。

第二点就是二维数组在初始化的适合需要注意,背包重量小于nums[0]的数是没法装的,需初始化为0。

另外还有一种思路:

  • dp[i] [j] : 从[0, i]区间中挑选一些正整数,每个数只能用一次,这些数的和恰好为 j
  • 递推公式:dp[i] [j] = dp[i - 1] [j] || dp[i - 1] [j - nums[i]]
  • 初始化:在num[0] < target 的情况下,第一个数只能让容积为自己的背包填满:dp[0] [num[0]] = true
class Solution {public boolean canPartition(int[] nums) {int sum = 0;for (int num : nums) sum+=num;if (sum % 2 == 1) return false;// target 相当于背包的容量int target = sum / 2;boolean[][] dp = new boolean[nums.length][target + 1];// 初始化,填满第一行的dp[0][nums[0]] 只有nums[0]本身if (nums[0] < target) dp[0][nums[0]] = true;//        System.out.print("dp[0] = " + Arrays.toString(dp[0]));
//        System.out.println();// 外层遍历物品数量for (int i = 1; i < nums.length; i++) {// 内层遍历背包for (int j = 0; j <= target; j++) {// 先取上一次的结果,后面进行修正dp[i][j] = dp[i-1][j];// 如果某个物品的重量恰好等于背包重量,则满足条件// 所以这一列的值都为trueif (nums[i] == j){dp[i][j] = true;
//                    System.out.print("***="+dp[i][j] + "\t\t");continue;}// 如果该物品小于背包的重量,就判断能否加入新的物品// dp[i-1][j]表示不放入背包,如果前面有满足条件,后面就一定可以满足// dp[i-1][j-nums[i]]表示放入背包,放入后判断放入背包的区间有没有满足条件的,就是左上if (nums[i] < j){dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]];}
//                System.out.print("dp="+dp[i][j] + "\t\t");}
//            System.out.println();}return dp[nums.length-1][target];}
}
http://www.tj-hxxt.cn/news/9213.html

相关文章:

  • 免费注册网站软件站长工具外链查询
  • 新乡网站建设国外b站推广网站
  • 做网站有弹窗叫什么新出的app推广在哪找
  • 电子烟网站建设百度seo搜索引擎优化厂家
  • 网站全屏视频怎么做刘连康seo培训哪家强
  • 做视频赚钱的网站小程序怎么引流推广
  • 常用网站域名网站定制设计
  • 成全视频免费观看在线看第2季站优云seo优化
  • 电子商务网站建设的步骤百度收录提交工具
  • 用js做网站百度竞价推广收费标准
  • 石湾手机网站建设大型网站建设方案
  • 做房产网站哪个好建站小程序
  • 网站的建设适合小学生的新闻事件
  • 哪个网站有摄影作品seo相关ppt
  • 网站开发主机的选择怎么把平台推广出去
  • 国内购物网站案例分析网站免费搭建平台
  • 网站群cmsseo超级外链工具免费
  • 建设网站前期准备工作最近一周的国内新闻
  • 做微商能利用的网站有哪些问题河南省网站
  • 网站seo策划方案设计google网站登录入口
  • 长春网站建设方案优化设计三年级上册语文答案
  • 免费b2b网站大全在线南宁seo优势
  • 用php做的网站实例女生学市场营销好吗
  • 公路建设市场信用信息系统网站c盘优化大师
  • 福州网站建设信息网站搜索引擎优化技术
  • 品牌设计logo图片seo诊断分析在线工具
  • 东营港新闻最新消息seo推广效果
  • 税务网站怎样查询建设项目趣丁号友情链接
  • 网站流量少学做电商需要多少钱
  • DW如何做明星的个人网站外贸网站营销推广