做网站的叫什么思耐wordpress 外贸 主题

做网站的叫什么思耐,wordpress 外贸 主题,佛山微网站建设哪家专业,免费网站怎么做出来的#x1f468;‍#x1f4bb;程序员三明治#xff1a;个人主页#x1f525; 个人专栏: 《设计模式精解》 《重学数据结构》#x1f91e;先做到 再看见#xff01; 目录01背包题目分析01背包解决方法完全背包题目分析完全背包解决方法LeetCode 518.零钱兑换II思路代码实现0…‍程序员三明治个人主页 个人专栏: 《设计模式精解》 《重学数据结构》先做到 再看见目录01背包题目分析01背包解决方法完全背包题目分析完全背包解决方法LeetCode 518.零钱兑换II思路代码实现01背包题目分析有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。每一件物品其实只有两个状态取或者不取所以可以使用回溯法搜索出所有的情况那么时间复杂度就是O(2^n)这里的n表示物品数量。所以暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化在下面的讲解我举一个例子物品为重量价值物品0115物品1320物品243001背包解决方法递归五部曲确定dp数组以及下标的含义dp[i][j] 表示从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少为什么需要用二维数组呢因为有两个维度需要分别表示物品 和 背包容量我们先看把物品0 放入背包的情况再看把物品1 放入背包背包容量为 0放不下物品0 或者物品1此时背包里的价值为0。背包容量为 1只能放下物品0背包里的价值为15。背包容量为 2只能放下物品0背包里的价值为15。背包容量为 3上一行同一状态背包只能放物品0这次也可以选择物品1了背包可以放物品1 或者 物品0物品1价值更大背包里的价值为20。背包容量为 4上一行同一状态背包只能放物品0这次也可以选择物品1了背包可以放下物品0 和 物品1背包价值为35。确定递推公式对于递推公式首先我们要明确有哪些方向可以推导出 dp[i][j]这里我们dp[1][4]的状态来举例求取 dp[1][4] 有两种情况放物品1还是不放物品1如果不放物品1 那么背包的价值应该是 dp[0][4] 即 容量为4的背包只放物品0的情况。如果放物品1那么背包要先留出物品1的容量目前容量是4物品1 的容量就是物品1的重量为3此时背包剩下容量为1。容量为1只考虑放物品0 的最大价值是 dp[0][1]这个值我们之前就计算过。所以 放物品1 的情况 dp[0][1] 物品1 的价值推导方向如图所以两种情况综合一起可以得出递归公式font stylecolor:rgb(71, 101, 130);background-color:rgba(27, 31, 35, 0.05);dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]);/font3. dp数组初始化首先从dp[i][j]的定义出发如果背包容量j为0的话即dp[i][0]无论是选取哪些物品背包价值总和一定为0。如图从递归公式可以看出i 是由 i-1 推导出来那么i为0的时候就一定要初始化。确定遍历顺序先遍历 物品还是先遍历背包重量呢其实都可以 但是先遍历物品更好理解。那么我先给出先遍历物品然后遍历背包重量的代码。for(inti1;in;i){for(intj0;jbagweight;j){if(jweight[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数组最终结果就是dp[2][4]。完全背包题目分析完全背包和01背包问题唯一不同的地方就是每种物品有无限件。在下面的讲解继续用之前的例子物品为重量价值物品0115物品1320物品2430完全背包解决方法确定dp数组以及下标的含义dp[i][j] 表示从下标为[0-i]的物品每个物品可以取无限次放进容量为j的背包价值总和最大是多少。确定递推公式这里依然拿dp[1][4]的状态来举例求取 dp[1][4] 有两种情况放物品1还是不放物品1如果不放物品1 那么背包的价值应该是 dp[0][4] 即 容量为4的背包只放物品0的情况。如果放物品1那么背包要先留出物品1的容量目前容量是4物品1 的容量就是物品1的重量为3此时背包剩下容量为1。容量为1只考虑放物品0 和物品1 的最大价值是 dp[1][1]注意 这里和01背包有所不同了在 01背包中背包先空留出物品1的容量此时容量为1只考虑放物品0的最大价值是 dp[0][1]因为01背包每个物品只有一个既然空出物品1那背包中也不会再有物品1而在完全背包中物品是可以放无限个所以 即使空出物品1空间重量那背包中也可能还有物品1所以此时我们依然考虑放 物品0 和 物品1 的最大价值即dp[1][1] 而不是 dp[0][1]、所以可以得出递推公式font stylecolor:rgb(71, 101, 130);background-color:rgba(27, 31, 35, 0.05);dp[i][j] max(dp[i - 1][j], dp[i][j - weight[i]] value[i]);/fontdp数组初始化如果背包容量j为0的话即dp[i][0]无论是选取哪些物品背包价值总和一定为0再看其他情况font stylecolor:rgb(71, 101, 130);background-color:rgba(27, 31, 35, 0.05);dp[i][j] max(dp[i - 1][j], dp[i][j - weight[i]] value[i]);/font可以看出有一个方向 i 是由 i-1 推导出来那么i为0的时候就一定要初始化。dp[0][j]即存放物品0的时候各个容量的背包所能存放的最大价值。for(intjweight[0];jbagWeight;j){dp[0][j]dp[0][j-weight[0]]value[0];}确定遍历顺序01背包二维DP数组先遍历物品还是先遍历背包都是可以的。因为两种遍历顺序对于二维dp数组来说递推公式所需要的值二维dp数组里对应的位置都有。举例推导dp数组LeetCode 518.零钱兑换II给你一个整数数组coins表示不同面额的硬币另给一个整数amount表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额返回0。假设每一种面额的硬币有无限个。题目数据保证结果符合 32 位带符号整数。示例 1输入amount 5, coins [1, 2, 5] 输出4 解释有四种方式可以凑成总金额 55 5221 52111 511111示例 2输入amount 3, coins [2] 输出0 解释只用面额 2 的硬币不能凑成总金额 3 。思路本题求的是装满这个背包的物品组合数是多少。因为每一种面额的硬币有无限个所以这是完全背包。动规五部曲确定dp数组以及下标的含义dp[i][j]使用 下标为[0, i]的coins[i]能够凑满j包括j这么大容量的包有dp[i][j]种组合方法。递推公式因为本题属于完全背包问题所以递推公式需要参考dp[i][j] max(dp[i - 1][j], dp[i][j - weight[i]] value[i])但考虑到我们的dp数组含义求的是组合个数所以本题的递推公式是dp[i][j] dp[i - 1][j] dp[i - 1][j - nums[i]]初始化以这个为例第一行如何初始化dp[0][0] 应该是多少背包空间为0装满「物品0」 的组合数有多少呢应该是 0 个 但如果 「物品0」 的 数值就是0呢 岂不是可以有无限个0 组合 和为0题目描述中说了font stylecolor:rgb(71, 101, 130);background-color:rgba(27, 31, 35, 0.05);1 coins.length 300/font和font stylecolor:rgba(38, 38, 38, 0.75);background-color:rgba(0, 10, 32, 0.03);1 coins[i] 5000/font所以不用考虑 物品数值为0的情况。dp[0][j]的含义用「物品0」即coins[0] 装满 背包容量为j的背包有几种组合方法。如果 j 可以整除 物品0那么装满背包就有1种组合方法。for(intj0;jamount;j){if(j%coins[0]0)dp[0][j]1;}最左列如何初始化呢dp[i][0] 的含义用物品i即coins[i] 装满容量为0的背包 有几种组合方法。都有一种方法即不装。所以 dp[i][0] 都初始化为1综上可以得出下图确定遍历顺序先遍历物品在遍历背包比较容易理解打印dp数组代码实现classSolution{publicintchange(intamount,int[]coins){int[][]dpnewint[coins.length][amount1];// 初始化最左列for(inti0;icoins.length;i){dp[i][0]1;}// 初始化最上行for(intj0;jamount;j){if(j%coins[0]0)dp[0][j]1;}// 开始遍历for(inti1;icoins.length;i){for(intj0;jamount;j){if(coins[i]j){dp[i][j]dp[i-1][j];}else{dp[i][j]dp[i-1][j]dp[i][j-coins[i]];}}}returndp[coins.length-1][amount];}}如果我的内容对你有帮助请辛苦动动您的手指为我点赞评论收藏。感谢大家!!