01背包问题的简单理解 灰太狼 2024-04-03 12:50 39阅读 0赞 对于0/1背包问题,是一类比较经典的问题,主要就是对于物品是否放入背包的一个考量,从难易程度上来说,个人感觉二维的比一维的更好理解. 对于二维,整个dp数组的推倒过程就是从左上到右下的一个过程,那么是具体怎么推倒的的: ![f34ca9e1da9e4a88b0b88808e65810e6.png][] ![ebbdf59cc33e4d20978a826854873a0c.png][] 以这个为例:dp\[i\]\[j\]表示的含义是对于第i个物品,在已经占用重量为j的情况下所获得的最大价值. 对于第i个物品,操作就很明显了,因为是0/1背包,那么只有放和不放两种,放的话,就要dp\[i-1\]\[j-weight\[i\]\] + value;不放,那就从上面的同层直接拿下来,也就是dp\[i-1\]\[j\]当中,所以比较好理解. 例题如下: [力扣][Link 1] 给你一个 **只包含正整数** 的 **非空** 数组 `nums` 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 输入:nums = [1,5,11,5] 输出:true 解释:数组可以分割成 [1, 5, 5] 和 [11] 。 class Solution { public boolean canPartition(int[] nums) { int sum_ = Arrays.stream(nums).sum(); if(sum_ % 2 != 0){ return false; } int sum_2 = sum_ / 2 ; System.out.println(sum_2); //容量是sum_,重量是nums[i] int[][] dp = new int [nums.length][sum_2 + 1]; for(int i = 0; i < sum_2; i++){ if(i < nums[0]){ dp[0][i] = 0; }else{ dp[0][i] = nums[0]; } } for(int i = 1; i < nums.length; i++){ for(int j = 1; j <= sum_2; 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]); } } } // for(int i = 0; i < nums.length; i++){ // for(int j = 0; j <= sum_2; j++){ // System.out.print(dp[i][j]); // System.out.print(" "); // } // System.out.println(); // } // System.out.print(dp[nums.length - 1][sum_2 - 1]); return dp[nums.length - 1][sum_2 ] == sum_2; } } 思路如下,将物品视位重量和价值相同的特殊物品,向背包中装填,如果恰好能装够一半的重量,那么则是符合要求的.难点在于:对于dp\[i\]\[j\]大小的定义,j代表包的容量,那么应该定义为物品总重量的一半+1,为什么加1?因为物品的重量是从1开始的,也就是说没有重量是0的物品,如果总的重量不加1,那么无法遍历到最后.对于物品数量也就是行数,则没有什么特殊要求. [f34ca9e1da9e4a88b0b88808e65810e6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/93f68c440d78492ca4223c5b25513c3b.png [ebbdf59cc33e4d20978a826854873a0c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/34bdf1537ad2421089185bd93b9fae9a.png [Link 1]: https://leetcode.cn/problems/partition-equal-subset-sum/
相关 01背包问题的简单理解 对于0/1背包问题,是一类比较经典的问题,主要就是对于物品是否放入背包的一个考量,从难易程度上来说,个人感觉二维的比一维的更好理解. 对于二维,整个dp数组的推倒过程就是从左 灰太狼/ 2024年04月03日 12:50/ 0 赞/ 40 阅读
相关 01背包问题 [0-1背包问题][0-1] Reference: https://www.jianshu.com/p/a66d5ce49df5 问题描述: 0-1背包问题:给定 ﹏ヽ暗。殇╰゛Y/ 2022年10月11日 13:40/ 0 赞/ 210 阅读
相关 01背包问题 1.题目 有N件物品和一个容量为V的背包。第i件物品的成本是c\[i\],价值是w\[i\]。求解将哪些物品装入背包可使价值总和最大,要求是:物品只能放一次。 2.分 系统管理员/ 2022年09月10日 11:27/ 0 赞/ 178 阅读
相关 01背包问题 ![Center][] ![Center 1][] [Center]: /images/20220616/e1a67e5ed0214bac8ec5293bc2b54 ╰+攻爆jí腚メ/ 2022年06月16日 14:46/ 0 赞/ 193 阅读
相关 01背包问题 public class package0_1 { int V[][] = new int[200][200];//物品选取,背包承重 int max( 约定不等于承诺〃/ 2022年06月08日 06:15/ 0 赞/ 193 阅读
相关 01背包问题 【例9.11】01背包问题 时间限制: 1000 ms 内存限制: 65536 KB 【题目描述】 一个旅行者有一个最多能装M公斤的背包,现在有n件物 淩亂°似流年/ 2022年06月08日 03:59/ 0 赞/ 184 阅读
相关 背包问题—01背包、完全背包 01背包问题 题目 有m件物品和一个容量为V 的背包。放入第i 件物品占用的体积是Vi,得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。 思路 这 末蓝、/ 2022年05月30日 10:10/ 0 赞/ 305 阅读
相关 01背包问题 简单背包问题 设有一个背包可以放入的物品重量为S,现有n件物品,重量分别是w1,w2,w3,…wn。 问能否从这n件物品中选择若干件放入背包中,使得放入的重量之和正好为S 痛定思痛。/ 2022年05月26日 12:18/ 0 赞/ 186 阅读
相关 01背包问题 转载:[https://blog.csdn.net/xp731574722/article/details/70766804][https_blog.csdn.net_xp73 怼烎@/ 2022年05月06日 15:00/ 0 赞/ 240 阅读
相关 背包问题01 题目 有N件物品和一个容量为V的背包。第i件物品的费用是c\[i\],价值是w\[i\]。求解将哪些物品装入背包可使价值总和最大。 基本思路 这是最基础的背包问题,特 左手的ㄟ右手/ 2022年01月29日 11:34/ 0 赞/ 284 阅读
还没有评论,来说两句吧...