vps网站访问不了,游戏推广群,pc网站建设有什么功能,如何做网站建设方案第九章 动态规划part04● 01背包问题#xff0c;你该了解这些#xff01;
● 01背包问题#xff0c;你该了解这些#xff01; 滚动数组
● 416. 分割等和子集 正式开始背包问题#xff0c;背包问题还是挺难的#xff0c;虽然大家可能看了很多背包问题模板代码#xf…第九章 动态规划part04● 01背包问题你该了解这些
● 01背包问题你该了解这些 滚动数组
● 416. 分割等和子集 正式开始背包问题背包问题还是挺难的虽然大家可能看了很多背包问题模板代码感觉挺简单但基本理解的都不够深入。 如果是直接从来没听过背包问题可以先看文字讲解慢慢了解 这是干什么的。如果做过背包类问题可以先看视频很多内容是自己平时没有考虑到位的。 背包问题力扣上没有原题大家先了解理论今天就安排一道具体题目。 详细布置 01背包问题 二维
https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html
视频讲解https://www.bilibili.com/video/BV1cg411g7Y6 01背包问题 一维
https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-2.html
视频讲解https://www.bilibili.com/video/BV1BU4y177kY 416. 分割等和子集
本题是 01背包的应用类题目
https://programmercarl.com/0416.%E5%88%86%E5%89%B2%E7%AD%89%E5%92%8C%E5%AD%90%E9%9B%86.html
视频讲解https://www.bilibili.com/video/BV1rt4y1N7jEday41
01背包 方法一:二维数组 import java.util.Scanner;public class Main{public static void main(String[] args){Scanner sc new Scanner(System.in);int n sc.nextInt();int bagweight sc.nextInt();int[] weight new int[n];int[] value new int[n];for(int i 0; i n; i){weight[i] sc.nextInt();}for(int i 0; in; i){value[i] sc.nextInt();}//dp[i][j]表示0~i的物品放在容量j的背包的最大价值int[][] dp new int[n][bagweight 1];//初始化,dp[i][j]来自dp[i - 1][j]和dp[i - 1][j - weight[i]],所以初始化第1行和第1列for(int j weight[0] ; j bagweight; j){dp[0][j] value[0];}for(int i 1; i n; i){//对于二维数组,先遍历物品还是背包容量都可以,因为都来自正上方和左上方for(int j 1; j bagweight; j){if(j weight[i]) 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[i][j]都是由dp[i-1][j或者j-weight[i]]得来的}}System.out.println(dp[n - 1][bagweight]);}} 方法二:一维数组 //把[i]这个维度压缩了,滚动数组的时候从后往前遍历,因为每个数据都是需要上一行正上的数据和上一行左边的数据,在同一行操作的时候如果优先改了左边的数据,右边的数据更新会被影响import java.util.Scanner;public class Main{public static void main(String[] args){Scanner sc new Scanner(System.in);int n sc.nextInt();int bagweight sc.nextInt();int[] weight new int[n];int[] value new int[n];for(int i 0; i n; i){weight[i] sc.nextInt();}for(int i 0; in; i){value[i] sc.nextInt();}int[] dp new int[bagweight 1];for(int j weight[0] ; j bagweight; j){dp[j] value[0];}for(int i 1; i n; i){for(int j bagweight; j weight[i]; j--){//if(j weight[i]) dp[j] dp[j];//判断多余了//else
dp[j] Math.max(dp[j], dp[j - weight[i]] value[i]);}}System.out.println(dp[bagweight]);}} 分割等和子集 //相当于weight[i]和value[i]相同的bagweight sum/2的01背包问题class Solution {public boolean canPartition(int[] nums) {if(nums null || nums.length 0) return false;int n nums.length;int sum 0;for(int num : nums) {sum num;}if(sum % 2 ! 0) return false;int target sum / 2;int[] dp new int[target 1];for(int i 0; i n; i) {for(int j target; j nums[i]; j--) {//物品 i 的重量是 nums[i]价值也是 nums[i]dp[j] Math.max(dp[j], dp[j - nums[i]] nums[i]);}//剪枝一下每一次完成內層的for-loop立即檢查是否dp[target] target優化時間複雜度26ms - 20ms//不用遍历完i,出现满足题意的装满的背包直接返回就行//为什么一定会在dp[target]处出现满足题意的背包,dp[target]有可能不正好是target,而是更大或者更小跳过正好是target的情况吗?//不可能,一个空间就是一个价值,target装满了最大就是target,只有可能是装满/不装满这两种情况,所以就是求最大价值的背包if(dp[target] target)return true;}return dp[target] target;}} 感谢大佬分享:
代码随想录-算法训练营day41【动态规划0401背包问题-滚动数组、分割等和子集】_分隔等和子集 [1,5,11,5] 背包 滚动数组-CSDN博客
