山东建设网站,宁波高端网站设计价格,做网站的技术风险,淘客怎么建网站做推广01背包问题 有n件物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i]#xff0c;得到的价值是value[i] 。每件物品只能用一次#xff0c;求解将哪些物品装入背包里物品价值总和最大。
例#xff1a;背包最大重量为4。
物品为#xff1a;
重量价值物品0115物品…01背包问题 有n件物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。
例背包最大重量为4。
物品为
重量价值物品0115物品1320物品2430问背包能背的物品最大价值是多少 一、二维dp数组01背包
1、确定dp数组以及下标的含义
dp[i][j]在下标[0,i]的物品任取放进容量为j的背包价值总和最大是多少 2、确定递推公式
如果背包重量小于物品 i 的重量那么就不把 i 放进背包里可得
所以递推公式为
dp[i][j]dp[i-1][j] 如果背包重量大于物品i的重量分类讨论 放物品idp[i][j]dp[i-1][j-weight[i]]value[i]不放物品idp[i][j]dp[i-1][j]所以递推公式为
dp[i][j]Math.max(dp[i-1][j-weight[i]]value[i],dp[i-1][j]) 3、dp数组初始化
① 根据dp的递推公式dp[i-1][j]可知i 由i-1推导出来(上面的元素)所以要初始化i0时的数组元素即dp[0][j]存放编号为0的物品时放入各个重量的状态最大价值总和。
当weight[0]j 时dp[0][j]0。背包容量比编号0的物品重量还小
当weight[0]j 时dp[0][j]value[0]。背包容量放足够放编号0物品 ② 根据dp[i-1][j-weight[i]]value[i]可知j 由j-weight[i] 推导出来(左上角的元素)所以要初始化j0时的元素即dp[i][0]0背包重量为0放不进去所以最大价值为0。 其它元素随意赋初始值因为会被覆盖。 4、确定遍历顺序
先遍历物品先横向遍历或者先遍历重量先遍历纵向都可以都可以保证左上方和上方已有值。
5、举例推导dp数组
public class Main {public static void main(String[] args) {int[] weight {1,3,4};int[] value {15,20,30};int bagSize 4;testWeightBagProblem(weight,value,bagSize);}/*** 动态规划获得结果* param weight 物品的重量* param value 物品的价值* param bagSize 背包的容量*/public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){// 创建dp数组int goods weight.length; // 获取物品的数量int[][] dp new int[goods][bagSize 1];// 初始化dp数组// 创建数组后其中默认的值就是0//i0,dp[0][j]for (int j 0; j bagSize; j) {if (weight[0]j){dp[0][j]0;}else if (weight[0]j){dp[0][j]value[0];}}//j0,dp[i][0]for (int i 0; i goods; i) {dp[i][0] 0;}// 填充dp数组for (int i 1; i weight.length; i) {for (int j 1; j bagSize; j) {if (j weight[i]) {/*** 当前背包的容量都没有当前物品i大的时候是不放物品i的* 那么前i-1个物品能放下的最大价值就是当前情况的最大价值*/dp[i][j] dp[i-1][j];} else {/*** 当前背包的容量可以放下物品i* 那么此时分两种情况* 1、不放物品i* 2、放物品i* 比较这两种情况下哪种背包中物品的最大价值最大*/dp[i][j] Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] value[i]);}}}// 打印dp数组for (int i 0; i goods; i) {for (int j 0; j bagSize; j) {System.out.print(dp[i][j] \t);}System.out.println(\n);}}
}
二、一维dp数组01背包滚动数组
行覆盖。把dp[i - 1]那一层拷贝到dp[i]上只用一维数组dp[j]
1、确定dp数组以及下标的含义
dp[j]容量为j的背包所背的物品价值可以最大为dp[j]。 2、一维dp数组的递推公式
不放物品 i 时dp[j]dp[j]相当于dp[i-1][j]放物品 i 时dp[j]dp[j-weight[i]]value[i]
递推公式为
dp[j]Math.max(dp[j],dp[j-weight[i]]value[i]) 3、一维dp数组初始化
题目给的价值都是正整数那么非0下标都初始化为0。dp[j]0
这样才能让dp数组在递归公式的过程中取的最大的价值而不是被初始值覆盖了。 4、一维dp数组遍历顺序
① 倒序背包从大到小为了保证物品i只被放入一次。
例物品0的重量weight[0] 1价值value[0] 15
如果正序遍历假设i0时
dp[1] dp[1 - weight[0]] value[0] 15
dp[2] dp[2 - weight[0]] value[0] 30
此时dp[2]就已经是30了意味着物品0被放入了两次所以不能正序遍历。
倒序就是先算dp[2]
dp[2] dp[2 - weight[0]] value[0] 15 dp数组已经都初始化为0
dp[1] dp[1 - weight[0]] value[0] 15
tips假设目前有背包容量为10可以装的最大价值 记为g[10]。即将进来的物品重量为6。价值为9。
如果不装该物品显然背包容量无变化这里对应二维数组其实就是取该格子上方的格子复制下来就是所说的滚动下来直接g[10[ g[10]这两个g[10]要搞清楚右边的g[10]是上一轮记录的也就是对应二维数组里上一层的值而左边是新的g[10]也就是对应二维数组里下一层的值。
如果装该物品则背包容量 g[10-6] g[4] 9 也就是 g[10] g[4] 6 ,这里的6显然就是新进来的物品的价值g[10]就是新记录的对应二维数组里下一层的值而这里的g[4]是对应二维数组里上一层的值通俗的来讲你要找到上一层也就是上一状态下 背包容量为4时的能装的最大价值用它来更新下一层的这一状态也就是加入了价值为9的物品的新状态。 这时候如果是正序遍历会怎么样g[10] g[4] 6 这个式子里的g[4]就不再是上一层的了因为你是正序啊g[4] 比g[10]提前更新那么此时程序已经没法读取到上一层的g[4]了新更新的下一层的g[4]覆盖掉了这里也就是为啥有题解说一件物品被拿了两次的原因。
② 先遍历物品再遍历背包容量
如果顺序反了dp[j]就会一直为最大值最终结果为3030303030 5、举例推导dp数组
一维dp分别用物品0物品1物品2 来遍历背包最终得到结果如下 public static void main(String[] args) {int[] weight {1, 3, 4};int[] value {15, 20, 30};int bagWight 4;testWeightBagProblem(weight, value, bagWight);}public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){int wLen weight.length;//定义dp数组dp[j]表示背包容量为j时能获得的最大价值int[] dp new int[bagWeight 1];//遍历顺序先遍历物品再遍历背包容量for (int i 0; i wLen; i){for (int j bagWeight; j weight[i]; j--){dp[j] Math.max(dp[j], dp[j - weight[i]] value[i]);}}//打印dp数组for (int j 0; j bagWeight; j){System.out.print(dp[j] );}} 416. 分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。 示例 1 输入nums [1,5,11,5] 输出true 解释数组可以分割成 [1, 5, 5] 和 [11] 。 示例 2 输入nums [1,2,3,5] 输出false 解释数组不能分割成两个元素和相等的子集。 问题分析
背包的体积为sum / 2背包要放入的商品集合里的元素重量为 元素的数值价值也为元素的数值背包如果正好装满说明找到了总和为 sum / 2 的子集。背包中每一个元素是不可重复放入。1、确定dp数组以及下标的含义
dp[j]背包总容量所能装的总重量是j放进物品后背的最大重量为dp[j]。 2、确定递推公式
01背包的递推公式为dp[j] max(dp[j], dp[j - weight[i]] value[i]);
本题相当于背包里放入数值那么物品i的重量是nums[i]其价值也是nums[i]。
所以递推公式dp[j] max(dp[j], dp[j - nums[i]] nums[i]) 3、dp数组初始化
dp[j]0数组初始化自动赋为0
这样才能让dp数组在递推的过程中取得最大的价值而不是被初始值覆盖了。 4、确定遍历顺序
如同01滚动数组使用一维dp物品遍历的for循环放在外层遍历背包的for循环放在内层且内层for循环倒序遍历 5、举例推导dp数组
若dp[target]target说明可以凑成两个总和相等的数组
class Solution {public boolean canPartition(int[] nums) {int sum0;for (int i0;i nums.length;i){sumsumnums[i];}if (sum%2!0) return false;//如果不是2的倍数就不能分成两个相等的数组int targetsum/2;int[] dpnew int[target1];for(int i0;i nums.length;i){for (int jtarget;jnums[i];j--){dp[j]Math.max(dp[j],dp[j-nums[i]]nums[i]);}}return dp[target]target;//背包的容量和背包的价值都是nums[i]}
}
文章转载自： http://www.morning.tqpds.cn.gov.cn.tqpds.cn http://www.morning.dwtdn.cn.gov.cn.dwtdn.cn http://www.morning.wdwfm.cn.gov.cn.wdwfm.cn http://www.morning.yjfzk.cn.gov.cn.yjfzk.cn http://www.morning.zcwwb.cn.gov.cn.zcwwb.cn http://www.morning.krdxz.cn.gov.cn.krdxz.cn http://www.morning.kxgn.cn.gov.cn.kxgn.cn http://www.morning.qmqgx.cn.gov.cn.qmqgx.cn http://www.morning.rgmls.cn.gov.cn.rgmls.cn http://www.morning.qmxsx.cn.gov.cn.qmxsx.cn http://www.morning.ywqsk.cn.gov.cn.ywqsk.cn http://www.morning.plqkz.cn.gov.cn.plqkz.cn http://www.morning.ctxt.cn.gov.cn.ctxt.cn http://www.morning.jrpmf.cn.gov.cn.jrpmf.cn http://www.morning.klyzg.cn.gov.cn.klyzg.cn http://www.morning.gtxrw.cn.gov.cn.gtxrw.cn http://www.morning.tgmfg.cn.gov.cn.tgmfg.cn http://www.morning.gnyhc.cn.gov.cn.gnyhc.cn http://www.morning.jcyyh.cn.gov.cn.jcyyh.cn http://www.morning.jlqn.cn.gov.cn.jlqn.cn http://www.morning.tcxzn.cn.gov.cn.tcxzn.cn http://www.morning.lpnpn.cn.gov.cn.lpnpn.cn http://www.morning.ymtbr.cn.gov.cn.ymtbr.cn http://www.morning.dfkmz.cn.gov.cn.dfkmz.cn http://www.morning.jwefry.cn.gov.cn.jwefry.cn http://www.morning.qkrgk.cn.gov.cn.qkrgk.cn http://www.morning.wjlkz.cn.gov.cn.wjlkz.cn http://www.morning.pqcbx.cn.gov.cn.pqcbx.cn http://www.morning.oumong.com.gov.cn.oumong.com http://www.morning.gyjld.cn.gov.cn.gyjld.cn http://www.morning.gybnk.cn.gov.cn.gybnk.cn http://www.morning.zhiheliuxue.com.gov.cn.zhiheliuxue.com http://www.morning.mhfbp.cn.gov.cn.mhfbp.cn http://www.morning.enjoinfo.cn.gov.cn.enjoinfo.cn http://www.morning.gsjw.cn.gov.cn.gsjw.cn http://www.morning.phxdc.cn.gov.cn.phxdc.cn http://www.morning.tktyh.cn.gov.cn.tktyh.cn http://www.morning.fbylq.cn.gov.cn.fbylq.cn http://www.morning.dnhdp.cn.gov.cn.dnhdp.cn http://www.morning.redhoma.com.gov.cn.redhoma.com http://www.morning.lqgtx.cn.gov.cn.lqgtx.cn http://www.morning.bpp999.com.gov.cn.bpp999.com http://www.morning.pbmg.cn.gov.cn.pbmg.cn http://www.morning.pbgnx.cn.gov.cn.pbgnx.cn http://www.morning.dkqbc.cn.gov.cn.dkqbc.cn http://www.morning.lveyue.com.gov.cn.lveyue.com http://www.morning.nhzxr.cn.gov.cn.nhzxr.cn http://www.morning.hqbk.cn.gov.cn.hqbk.cn http://www.morning.sfrw.cn.gov.cn.sfrw.cn http://www.morning.gcysq.cn.gov.cn.gcysq.cn http://www.morning.jjzrh.cn.gov.cn.jjzrh.cn http://www.morning.cwznh.cn.gov.cn.cwznh.cn http://www.morning.rfxg.cn.gov.cn.rfxg.cn http://www.morning.ywxln.cn.gov.cn.ywxln.cn http://www.morning.qcfcz.cn.gov.cn.qcfcz.cn http://www.morning.fgrkc.cn.gov.cn.fgrkc.cn http://www.morning.mkbc.cn.gov.cn.mkbc.cn http://www.morning.fgqbx.cn.gov.cn.fgqbx.cn http://www.morning.lxqyf.cn.gov.cn.lxqyf.cn http://www.morning.pqkrh.cn.gov.cn.pqkrh.cn http://www.morning.mqwnz.cn.gov.cn.mqwnz.cn http://www.morning.nbnpb.cn.gov.cn.nbnpb.cn http://www.morning.qshxh.cn.gov.cn.qshxh.cn http://www.morning.rcjyc.cn.gov.cn.rcjyc.cn http://www.morning.wrbnh.cn.gov.cn.wrbnh.cn http://www.morning.swkpq.cn.gov.cn.swkpq.cn http://www.morning.fqmcc.cn.gov.cn.fqmcc.cn http://www.morning.gcqdp.cn.gov.cn.gcqdp.cn http://www.morning.dspqc.cn.gov.cn.dspqc.cn http://www.morning.wbxbj.cn.gov.cn.wbxbj.cn http://www.morning.nmfml.cn.gov.cn.nmfml.cn http://www.morning.wnbpm.cn.gov.cn.wnbpm.cn http://www.morning.wdhhz.cn.gov.cn.wdhhz.cn http://www.morning.fpngg.cn.gov.cn.fpngg.cn http://www.morning.fgxr.cn.gov.cn.fgxr.cn http://www.morning.rbbzn.cn.gov.cn.rbbzn.cn http://www.morning.gkdhf.cn.gov.cn.gkdhf.cn http://www.morning.htjwz.cn.gov.cn.htjwz.cn http://www.morning.zkrzb.cn.gov.cn.zkrzb.cn http://www.morning.qfcnp.cn.gov.cn.qfcnp.cn
