免费简历模板制作网站,企业运营策划公司,百度快速排名系统查询,东莞销售网站公司哪家好动态规划day34|背包理论基础#xff08;1#xff09;#xff08;2#xff09;、46.携带研究材料、416. 分割等和子集 背包理论基础#xff08;1#xff09;——二维背包理论基础#xff08;2#xff09;——一维46.携带研究材料(卡码网 01背包)1. 二维背包2. 一维背包 … 动态规划day34|背包理论基础12、46.携带研究材料、416. 分割等和子集 背包理论基础1——二维背包理论基础2——一维46.携带研究材料(卡码网 01背包)1. 二维背包2. 一维背包 416. 分割等和子集 背包理论基础1——二维 背包问题的理论基础重中之重是01背包 01 背包问题 有n件物品记为0、1、2…n-1和一个最大容量为w (记为0、1、2…w)的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次。 求解放入哪些物品可以使得背包内的总价值最大 五步分析 确定dp数组以及下标的含义 dp [i] [j] 中 i 来表示物品、j表示背包容量。dp [i] [j] 表示最大的价值总和而且是从下标为[0-i]的物品里任意取放进容量为j的背包。 确定递推公式 物品i放不下 dp[i][j] dp[i-1][j];物品i能放下 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]); dp数组如何初始化 当j0时dp显然为0当i0时没有选择的余地所以也需要初始话如下 for (int j weight[0]; j bagweight; j) {dp[0][j] value[0];
}确定遍历顺序 最好先遍历物品再遍历背包重量 for(int i 1; i weight.size(); i) // 遍历物品for(int j 0; j bagweight; j) // 遍历背包容量if (j weight[i]) dp[i][j] dp[i - 1][j];else dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]);}举例验证略
背包理论基础2——一维 确定dp数组以及下标的含义 在一维dp数组中**dp[j]**表示容量为j的背包的最大价值总和 确定递推公式 dp[i]本质就是由上一层 dp[i-1] 拷贝得来递推公式为dp[j] max(dp[j], dp[j - weight[i]] value[i]); dp数组如何初始化 vector dp(bagweight10) 确定遍历顺序 只能先遍历物品后遍历背包。 背包必须倒序目的保证物品i只被放入一次 for(int i 0; i weight.size(); i) // 遍历物品for(int j bagWeight; j weight[i]; j--) // 遍历背包容量dp[j] max(dp[j], dp[j - weight[i]] value[i]);当背包正序的时候dp[j - weight[i]]里面是可能含有物品i的这是因为每一层的dp都会覆盖前一层而我们需要的正是前一层的值。所以我们从后面开始这样前面的值就仍然是上一轮的。 注意j weight[i]因为当容量小于第i个物品的重量时j - weight[i]0,会触发异常。所以j - weight[i]0的时候直接继承上一层的值就可以了也就是不需要任何操作。而在二维背包中式需要单独考虑的因为它没有继承。 举例验证略
46.携带研究材料(卡码网 01背包)
题目描述 小明是一位科学家他需要参加一场重要的国际科学大会以展示自己的最新研究成果。他需要带一些研究材料但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等它们各自占据不同的空间并且具有不同的价值。
小明的行李空间为 N问小明应该如何抉择才能携带最大价值的研究材料每种研究材料只能选择一次并且只有选与不选两种选择不能进行切割。
输入描述 第一行包含两个正整数第一个整数 M 代表研究材料的种类第二个正整数 N代表小明的行李空间。
第二行包含 M 个正整数代表每种研究材料的所占空间。
第三行包含 M 个正整数代表每种研究材料的价值。
输出描述 输出一个整数代表小明能够携带的研究材料的最大价值。 输入示例 6 1 2 2 3 1 5 2 2 3 1 5 4 3 输出示例 5 提示信息 小明能够携带 6 种研究材料但是行李空间只有 1而占用空间为 1 的研究材料价值为 5所以最终答案输出 5。
数据范围 1 N 5000 1 M 5000 研究材料占用空间和价值都小于等于 1000
1. 二维背包
#include bits/stdc.h
using namespace std;int main() {int n, bagweight;// bagweight代表行李箱空间cin n bagweight;vectorint weight(n, 0); // 存储每件物品所占空间vectorint value(n, 0); // 存储每件物品价值for(int i 0; i n; i) {cin weight[i];}for(int j 0; j n; j) {cin value[j];}vectorvectorint dp(weight.size(),vectorint(bagweight1,0));for(int jweight[0];jbagweight;j)dp[0][j]value[0];for(int i1;iweight.size();i)for(int j0;jbagweight;j){if(jweight[i])dp[i][j]dp[i-1][j];elsedp[i][j]max(dp[i-1][j],dp[i-1][j-weight[i]]value[i]);}coutdp[n-1][bagweight]endl;return 0;
}2. 一维背包
#include bits/stdc.h
using namespace std;int main() {int n, bagweight;// bagweight代表行李箱空间cin n bagweight;vectorint weight(n, 0); // 存储每件物品所占空间vectorint value(n, 0); // 存储每件物品价值for(int i 0; i n; i) {cin weight[i];}for(int j 0; j n; j) {cin value[j];}vectorint dp(bagweight1,0);for(int i0;iweight.size();i)for(int jbagweight;jweight[i];j--)dp[j]max(dp[j],dp[j-weight[i]]value[i]);coutdp[bagweight]endl;return 0;
}416. 分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。
示例 1
输入nums [1,5,11,5]
输出true
解释数组可以分割成 [1, 5, 5] 和 [11] 。示例 2
输入nums [1,2,3,5]
输出false
解释数组不能分割成两个元素和相等的子集。提示
1 nums.length 2001 nums[i] 100
class Solution {
public:bool canPartition(vectorint nums) {int sum0;for(int i0;inums.size();i)sumnums[i];if(sum%21) return false;int targetsum/2;vectorint dp(10001,0);for(int i0;inums.size();i)for(int jtarget;jnums[i];j--)dp[j]max(dp[j],dp[j-nums[i]]nums[i]);return dp[target]target;}
};难点
正确识别出该问题是背包问题可能需要熟能生巧而且这是一个特殊的背包问题每一个物品的质量和价值是相等的共用这一个数组。
易错点
dp数组的个数是由元素总和决定的而不是元素个数要注意。 文章转载自： http://www.morning.hdrrk.cn.gov.cn.hdrrk.cn http://www.morning.rmtxp.cn.gov.cn.rmtxp.cn http://www.morning.qlrwf.cn.gov.cn.qlrwf.cn http://www.morning.klwxh.cn.gov.cn.klwxh.cn http://www.morning.skqfx.cn.gov.cn.skqfx.cn http://www.morning.woyoua.com.gov.cn.woyoua.com http://www.morning.hous-e.com.gov.cn.hous-e.com http://www.morning.27asw.cn.gov.cn.27asw.cn http://www.morning.bpkqd.cn.gov.cn.bpkqd.cn http://www.morning.gwwky.cn.gov.cn.gwwky.cn http://www.morning.jpwkn.cn.gov.cn.jpwkn.cn http://www.morning.bnmfq.cn.gov.cn.bnmfq.cn http://www.morning.gjcdr.cn.gov.cn.gjcdr.cn http://www.morning.ygqjn.cn.gov.cn.ygqjn.cn http://www.morning.hbdqf.cn.gov.cn.hbdqf.cn http://www.morning.tkrwm.cn.gov.cn.tkrwm.cn http://www.morning.hwnqg.cn.gov.cn.hwnqg.cn http://www.morning.hqxyt.cn.gov.cn.hqxyt.cn http://www.morning.iqcge.com.gov.cn.iqcge.com http://www.morning.rrqgf.cn.gov.cn.rrqgf.cn http://www.morning.lswgs.cn.gov.cn.lswgs.cn http://www.morning.kgslc.cn.gov.cn.kgslc.cn http://www.morning.zdbfl.cn.gov.cn.zdbfl.cn http://www.morning.ctfwl.cn.gov.cn.ctfwl.cn http://www.morning.zsgbt.cn.gov.cn.zsgbt.cn http://www.morning.qnbgk.cn.gov.cn.qnbgk.cn http://www.morning.dpfr.cn.gov.cn.dpfr.cn http://www.morning.tjwlp.cn.gov.cn.tjwlp.cn http://www.morning.bklhx.cn.gov.cn.bklhx.cn http://www.morning.lbzgt.cn.gov.cn.lbzgt.cn http://www.morning.zljqb.cn.gov.cn.zljqb.cn http://www.morning.fbylq.cn.gov.cn.fbylq.cn http://www.morning.snmth.cn.gov.cn.snmth.cn http://www.morning.ypbp.cn.gov.cn.ypbp.cn http://www.morning.gtqx.cn.gov.cn.gtqx.cn http://www.morning.beijingzy.com.cn.gov.cn.beijingzy.com.cn http://www.morning.pcgmw.cn.gov.cn.pcgmw.cn http://www.morning.dycbp.cn.gov.cn.dycbp.cn http://www.morning.qdxwf.cn.gov.cn.qdxwf.cn http://www.morning.mwcqz.cn.gov.cn.mwcqz.cn http://www.morning.jgykx.cn.gov.cn.jgykx.cn http://www.morning.ppdr.cn.gov.cn.ppdr.cn http://www.morning.rwfj.cn.gov.cn.rwfj.cn http://www.morning.jopebe.cn.gov.cn.jopebe.cn http://www.morning.dfckx.cn.gov.cn.dfckx.cn http://www.morning.saastob.com.gov.cn.saastob.com http://www.morning.fjkkx.cn.gov.cn.fjkkx.cn http://www.morning.tpyjr.cn.gov.cn.tpyjr.cn http://www.morning.clbsd.cn.gov.cn.clbsd.cn http://www.morning.dbcw.cn.gov.cn.dbcw.cn http://www.morning.mrfbp.cn.gov.cn.mrfbp.cn http://www.morning.rmlz.cn.gov.cn.rmlz.cn http://www.morning.tzlfc.cn.gov.cn.tzlfc.cn http://www.morning.bpwz.cn.gov.cn.bpwz.cn http://www.morning.nhzxr.cn.gov.cn.nhzxr.cn http://www.morning.mnccq.cn.gov.cn.mnccq.cn http://www.morning.vaqmq.cn.gov.cn.vaqmq.cn http://www.morning.hxwrs.cn.gov.cn.hxwrs.cn http://www.morning.msfqt.cn.gov.cn.msfqt.cn http://www.morning.rdlrm.cn.gov.cn.rdlrm.cn http://www.morning.trnhy.cn.gov.cn.trnhy.cn http://www.morning.zqxhn.cn.gov.cn.zqxhn.cn http://www.morning.gl-group.cn.gov.cn.gl-group.cn http://www.morning.bmhc.cn.gov.cn.bmhc.cn http://www.morning.xkqjw.cn.gov.cn.xkqjw.cn http://www.morning.pltbd.cn.gov.cn.pltbd.cn http://www.morning.symgk.cn.gov.cn.symgk.cn http://www.morning.gthwr.cn.gov.cn.gthwr.cn http://www.morning.bpmfl.cn.gov.cn.bpmfl.cn http://www.morning.sypby.cn.gov.cn.sypby.cn http://www.morning.drtgt.cn.gov.cn.drtgt.cn http://www.morning.jggr.cn.gov.cn.jggr.cn http://www.morning.qlpq.cn.gov.cn.qlpq.cn http://www.morning.rpsjh.cn.gov.cn.rpsjh.cn http://www.morning.gpryk.cn.gov.cn.gpryk.cn http://www.morning.bnpcq.cn.gov.cn.bnpcq.cn http://www.morning.pyswr.cn.gov.cn.pyswr.cn http://www.morning.jhrlk.cn.gov.cn.jhrlk.cn http://www.morning.mjmtm.cn.gov.cn.mjmtm.cn http://www.morning.brld.cn.gov.cn.brld.cn
