jsp网站建设项目实战 pdf,以下区域不属于官方网站,dx网站是哪家公司做的,seo高手培训目录
什么是背包问题#xff1f;
动态规划问题的一般解决办法#xff1a;
0-1背包问题#xff1a;
0 - 1背包类问题 分割等和子集#xff1a;
完全背包问题#xff1a;
完全背包类问题 零钱兑换II: 什么是背包问题#xff1f;
背包问题(Knapsack problem)是一种…目录
什么是背包问题
动态规划问题的一般解决办法
0-1背包问题
0 - 1背包类问题 分割等和子集
完全背包问题
完全背包类问题 零钱兑换II: 什么是背包问题
背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为给定一组物品每种物品都有自己的重量和价格在限定的总重量内我们如何选择才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题即在总重量不超过W的前提下总价值是否能达到V它是在1978年由Merkle和Hellman提出的。
动态规划问题的一般解决办法
动态规划无非就是利用历史记录来避免我们的重复计算。而这些历史记录我们得需要一些变量来保存一般是用一维数组或者二维数组来保存。下面我们先来讲下做动态规划题很重要的三个步骤: 步骤一:定义dp数组元素的含义步骤二:找出数组元素之间的关系式(也就是我们所熟知的状态转移方程)第三步骤找出初始值base case
接下来的题目我们会按照这三个步骤来解释说明
前言本文包含动态规划中的经典背包问题有关背包问题的描述如下
在动态规划中背包问题是一个经典的优化问题它可以分为0-1背包问题和完全背包问题两种类型。下面我们就来看看这两个问题
0-1背包问题
问题描述
给你一个可装载重量为 W 的背包和 N 个物品每个物品有重量和价值两个属性。其中第 i 个物品的重量为 wt[i]价值为 val[i]。现在让你用这个背包装物品每个物品只能用一次在不超过被包容量的前提下最多能装的价值是多少 步骤一:定义dp数组元素的含义
由于状态有两个就是「背包的容量」和「可选择的物品」这里我们就需要用到一个二维的dp
数组如下为dp数组的定义
dp[i][w] 的定义如下对于前 i 个物品当前背包的容量为 w这种情况下可以装的最大价值是 dp[i][w]
步骤二:找出数组元素之间的关系式(也就是我们所熟知的状态转移方程)
1.如果你没有把这第 i 个物品装入背包那么很显然最大价值 dp[i][w] 应该等于 dp[i-1][w]继承之前的结果(翻译一下就是不装入第i个物品相当于对前 i - 1 个物品进行选择对应此时的背包容量w)。即此时的状态转移方程是dp[ i ][ w ] dp[ i - 1 ][ w ]
2.如果你把这第 i 个物品装入了背包,此时背包剩余容量为 w - wt[ i - 1 ](wt数组下标是从0开始的, wt[ i - 1 ] 相当于第 i 个物品的重量val 也一样)
则此时的状态转移方程是dp[ i ][ w ] dp[ i - 1 ][ w - wt[ i - 1] ] val[ i - 1 ]
第三步骤找出初始值base case
这题的base case 相对简单当物品个数为0或则背包当前容量为0时dp[ i ][ w ] 都等于0
按照上述的状态转移方程我们可以填出对应dp表格以图中的例子为例 有了上述铺垫后动态规划的代码就很好实现了具体代码如下
int knapsack(int W, int N, int[] wt, int[] val) {assert N wt.length;// base case 已初始化数组自动全部初始化为0int[][] dp new int[N 1][W 1];for (int i 1; i N; i) {for (int w 1; w W; w) {if (w - wt[i - 1] 0) {// 这种情况下只能选择不装入背包dp[i][w] dp[i - 1][w];} else {// 装入或者不装入背包择优dp[i][w] Math.max(dp[i - 1][w - wt[i-1]] val[i-1], dp[i - 1][w]);}}}return dp[N][W];
}有了上面的一定了解后我们来看看0 - 1背包的类似题
0 - 1背包类问题 分割等和子集
看一下力扣第 416 题「分割等和子集open in new window」
题目描述输入一个只包含正整数的非空数组 nums请你写一个算法判断这个数组是否可以被分割成两个子集使得两个子集的元素和相等。对应函数签名如下 我们可以将这个问题转化为0 - 1背包问题具体做法
这个问题相当于给一个可装载重量为 sum / 2 的背包和 N 个物品每个物品的重量为 nums[i]。现在让你装物品是否存在一种装法能够恰好将背包装满按照上述解题思路就是 步骤一:定义dp数组元素的含义
dp[i][j] x 表示对于前 i 个物品i 从 1 开始计数当前背包的容量为 j 时若 x 为 true则说明可以恰好将背包装满若 x 为 false则说明不能恰好将背包装满。
步骤二:找出数组元素之间的关系式(也就是我们所熟知的状态转移方程)
与上面类似这里就直接给出来了
1.不把这第 i 个物品装入背包dp[ i ][ j ] dp[ i - 1 ][ j ]
2.把这第i个物品装入背包dp[ i ][ j ] dp[ i - 1][ j - nums[ i - 1 ] ]
第三步骤找出初始值base case
当背包容量为0时sum / 2 0这时无论物体有多少个都可以满足条件就是什么都不装嘛
ok接下来看完整代码
boolean canPartition(int[] nums) {int sum 0;for (int num : nums) sum num;// 和为奇数时不可能划分成两个和相等的集合if (sum % 2 ! 0) return false;int n nums.length;sum sum / 2;boolean[][] dp new boolean[n 1][sum 1];// base casefor (int i 0; i n; i)dp[i][0] true;for (int i 1; i n; i) {for (int j 1; j sum; j) {if (j - nums[i - 1] 0) {// 背包容量不足不能装入第 i 个物品dp[i][j] dp[i - 1][j];} else {// 装入或不装入背包dp[i][j] dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];}}}return dp[n][sum];
}完全背包问题
完全背包问题与0-1背包问题类似但不同之处在于每个物品可以选择放入背包多次数量无限即每个物品的选择是一个无限的选择。我们给出对应的解题方法 步骤一:定义dp数组元素的含义
若只使用前 i 个物品可以重复使用当背包容量为 j 时能装入背包的最大价值为dp[i][w]
步骤二:找出数组元素之间的关系式(也就是我们所熟知的状态转移方程)
1.不将第i个物品装入背包此时dp[ i ][ w ] dp[ i - 1 ][ w ]
2.将第i个物品装入背包此时:dp[ i ][ w ] dp[ i ][ w -wt[ i - 1] ] val[ i - 1 ]
第三步骤找出初始值base case
这题与0 - 1的bas背包的base case 一致当物品个数为0或者背包当前容量为0时dp[ i ][ w ] 都等于0
对应的动态规划代码为
int fullBackpack(int W, int N, int[] wt, int[] val) {assert N wt.length;// base case 已初始化数组自动全部初始化为0int[][] dp new int[N 1][W 1];for (int i 1; i N; i) {for (int w 1; w W; w) {if (w - wt[i - 1] 0) {// 这种情况下只能选择不装入背包dp[i][w] dp[i - 1][w];} else {// 装入或者不装入背包择优dp[i][w] Math.max(dp[i][w - wt[i-1]] val[i-1], dp[i - 1][w]);}}}return dp[N][W];
}完全背包类问题 零钱兑换II:
这是力扣第 518 题「零钱兑换 IIopen in new window」题目描述
给定不同面额的硬币 coins 和一个总金额 amount写一个函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。对应函数签名如下 我们可以把这个问题转化为完全背包问题的描述形式
有一个背包最大容量为 amount有一系列物品 coins每个物品的重量为 coins[i]每个物品的数量无限。请问有多少种方法能够把背包恰好装满按照动态规划三步走 步骤一:定义dp数组元素的含义
dp[i][j] 的定义如下若只使用前 i 个物品可以重复使用当背包容量为 j 时有 dp[i][j] 种方法可以装满背包。
步骤二:找出数组元素之间的关系式(也就是我们所熟知的状态转移方程)
1.如果你不把这第 i 个物品装入背包也就是说你不使用 coins[i-1] 这个面值的硬币那么凑出面额 j 的方法数 dp[i][j] 应该等于 dp[i-1][j]继承之前的结果
即状态转移方程为dp[ i ][ j ] dp[ i -1 ][ j ]
2.如果你把这第 i 个物品装入了背包也就是说你使用 coins[i-1] 这个面值的硬币那么 dp[i][j] 应该等于 dp[i][j-coins[i-1]]。
即状态转移方程为dp[ i ][ j ] dp[ i ][ j - coins[ i - 1] ]
第三步骤找出初始值base case
base case 为 dp[0][..] 0, dp[..][0] 1。i 0 代表不使用任何硬币面值这种情况下显然无法凑出任何金额j 0 代表需要凑出的目标金额为 0那么什么都不做就是唯一的一种凑法。
写出动态规划代码
int change(int amount, int[] coins) {int n coins.length;int[][] dp int[n 1][amount 1];// base casefor (int i 0; i n; i) dp[i][0] 1;for (int i 1; i n; i) {for (int j 1; j amount; j)//装入背包或者不装入加起来if (j - coins[i-1] 0)dp[i][j] dp[i - 1][j] dp[i][j - coins[i-1]];else // 0 只能选择不装入背包dp[i][j] dp[i - 1][j];}return dp[n][amount];
}结语 写博客不仅仅是为了分享学习经历同时这也有利于我巩固自己的知识点总结该知识点由于作者水平有限对文章有任何问题的还请指出接受大家的批评让我改进。同时也希望读者们不吝啬你们的点赞收藏关注你们的鼓励是我创作的最大动力
