中国旅游网站建设现状及发展趋势分析,河北大城县网站建设公司,网站开发用什么字体,miy188coo免费入口什么是01背包问题#xff1f;
有 N 件物品和一个最多能被重量为 W 的背包。第i件物品的重量是 weight[i]#xff0c;得到的价值是 value[i] 。每件物品只能用一次#xff0c;求解将哪些物品装入背包里物品价值总和最大。
解题思路#xff1a;
确定 dp 数组及下标的含义,…什么是01背包问题
有 N 件物品和一个最多能被重量为 W 的背包。第i件物品的重量是 weight[i]得到的价值是 value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。
解题思路
确定 dp 数组及下标的含义,定义一个数组dp[ i ] [ j ]i为当前物品的编号j为当前背包能容纳的质量dp[i][j] 表示背包容量为 j 时能获得的最大价值。确定递推公式:根据第一步 dp 数组的定义可知当我们遍历到第 i 个物品时可以选择将第 i 个物品装入背包也可以选择不装这两种情况分别所对应的最大价值如下当weight[ i ]j时装入dp[ i ] [ j ] dp[ i-1] [ j - weight[i]] value[i] —— 如果装入第 i 个物品则在装入之前需要背包先空出第 i 个物品的容量 weight[i]此时背包所获的的最大价值为 dp[ i ][j - weight[i]]然后再加上第 i 个物品的价值 value[i]当weight[ i ]j时不装dp[ i ][ j ] dp[ i-1 ][ j ] —— 如果不装入第 i 个物品就用除第 i 个物品之外的其它物品填满容量为 j 的背包此时的最大价值就是 dp[ i-1 ][ j ]最终 dp[ i] [ j ] 取装入或者不装入第 i 个物品所获得的价值中最大的那个即dp[ i ] [ j ] max(dp[ i-1][ j ], dp[ i-1][j - weight[i]] value[i])dp[i][j] 递推公式 如果求背包能装的最大重量dp[ i ][ j ] Math.max(dp[ i-1][ j ], dp[ i-1][j - weight[i]] value[i]);如果求装满容量为 j 的背包的方法数dp[i][j] dp[ i-1 ][ j ];初始化是严格按照dp 数组的定义来的当 j 为0时背包的容量为0所能获取的最大价值 dp[i][0] 也是0然后开始从第一个物品开始遍历
什么题目能用01背包解决呢
一堆东西一组数按照一定的方式进行组合、处理能否凑成某种最值状态或者凑成某种状态的方法数。能否拆分抽象成01背包的四要素背包容量、物品编号、物品质量、物品价值。如果可以这道题目可以使用01背包来解决。
例子:
力扣题目分割等和子集
LeetCode链接416. 分割等和子集 给你一个 只包含正整数的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。 示例 1 输入nums [1,5,11,5] 输出true 解释数组可以分割成 [1, 5, 5] 和 [11] 。 示例 2 输入nums [1,2,3,5] 输出false 解释数组不能分割成两个元素和相等的子集。 提示 1 nums.length 200 1 nums[i] 100 题目分析
假设原数组内数字总和为 sum若分成两个子集的元素和相等则每个子集和为 sum / 2即“是否能从非空数组 nums 中选出一些数这些数的和能够达到sum / 2 “。那么我们可以发现这道题目符合01背包的概念。将这道题目抽象为01背包问题背包的容量为sum / 2,物品就是数组的元素物品编号是数组元素的下标、物品质量为数组元素的大小、物品价值也是数组元素的大小。
解题思路
这道题要解决的是数组中是否能选出几个元素加起来的值等于数组元素总和的一半。
定义一个boolean[ i ] [ j ]数组来存储当前sum/2j 时能不能选出元素来凑成sum/2.如果能boolean[ i ] [ j ]的值为true不能为falsei表示数组元素下标j表示sum/2为j时。如果不选取任何正整数则被选取的元素等于 0。因此对于所有 0≤in都有 dp[i][0]true。当 i0时只有一个正整数 nums[0] 可以被选取因此 dp[0][nums[0]]true。 如果 j≥nums[i]则对于当前的数字 nums[i]可以选取也可以不选取两种情况只要有一个为 true就有 dp[i][j]true 如果不选取 nums[i]则 dp[i][j]dp[i-1][j] 如果选取 nums[i]则dp[i][j]dp[i−1][j−nums[i]] 如果 jnums[i]j 则在选取的数字的和等于 j 的情况下无法选取当前的数字 nums[i]因此有dp[i][j]dp[i−1][j]。 最终得到 dp[n-1] [total]即为答案 class Solution {public boolean canPartition(int[] nums) {Arrays.sort(nums); int n nums.length;if(n2){return false;}int sum0;for(int i : nums ){sumi;}int total sum/2;if(sum%2!0){return false;}if(nums[n-1]total){return false;}boolean [][] dp new boolean[n][total1];for(int i1;in;i){dp[i][0] true;}dp[0][nums[0]] true;for(int i1;in;i){int m nums[i];for(int j1;jtotal;j){if(mj){dp[i][j] dp[i-1][j] | dp[i-1][j-m];}else{dp[i][j] dp[i-1][j];}}}return dp[n-1] [total];}
} 力扣题目最后一块石头的重量 II
LeetCode链接1049. 最后一块石头的重量 II 有一堆石头用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合从中选出任意两块石头然后将它们一起粉碎。假设石头的重量分别为 x 和 y且 x y。那么粉碎的可能结果如下 如果 x y那么两块石头都会被完全粉碎 如果 x ! y那么重量为 x 的石头将会完全粉碎而重量为 y 的石头新重量为 y-x。 最后最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下就返回 0。 题目分析
根据题目描述当所有的石头都粉碎完时石头的重量最小。因此可以将石头分为两堆小的一堆、大的一堆。当小的一堆石头的重量无线接近甚至等于所有石头重量的一半的时候剩余的石头重量最小。因此很明显本题目符合01背包的特征。背包最大容量可以抽象为所有石头的一半质量物品可以抽象为石头。
解题思路
定义一个维度为[n 1][total 1]的数组 dp[i][j] 表示当石头重量的一半为j的时候要被粉碎石头的重量i表示为石头的编号j表示石头重量的一半。 当 i0没有任何石头总重量一定是 0对于任意 0≤j≤sum/2dp[0][j]0 如果 jstones[i−1]则不能选取当前石头最大总重量为在前 i−1块石头中选取且总重量不超过 j 的情况下的最大总重量因此最大总重量为 dp[i−1][j] 如果 j≥stones[i−1]则可以不选取或选取当前石头选择其中的最大总重量。如果不选取当前石头则在前 i−1块石头中选取石头时总重量不超过 j最大总重量为 dp[i−1][j]如果选取当前石头则在前 i−1块石头中选取石头时总重量不超过 j−stones[i−1]前 i−1块石头的最大重量为 dp[i−1][j−stones[i−1]]当前石头的重量为 stones[i−1]最大总重量为 dp[i−1][j−stones[i−1]]stones[i−1]。 动态规划的状态转移方程如下 如果 jstones[i−1]则 dp[i][j]dp[i−1][j] 如果 j≥stones[i−1]则 dp[i][j]max(dp[i−1][j],dp[i−1][j−stones[i−1]]stones[i−1]) 2*dp[n][total]为粉碎石头的最大重量粉碎石头时两边的石头都要消耗的所以乘2 最后sum - 2 * dp[n][total]则为最终答案
class Solution {public int lastStoneWeightII(int[] stones) {int n stones.length;if(n2){return stones[0];}int sum 0;for (int stone : stones) {sum stone;}int total sum / 2;int[][] dp new int[n 1][total 1];for (int i 1; i n; i) {for (int j 0; j total; j) {if (j stones[i - 1]) {dp[i][j] dp[i - 1][j];} else {dp[i][j] Math.max(dp[i - 1][j], dp[i - 1][j - stones[i - 1]] stones[i - 1]);}}}return sum - 2 * dp[n][total];}
}
