企业官网建设流程全解析

新网 网站建设,如何创造网站,免费网站空间 - 百度,网站设计合同动态规划:01背包问题 情景 现在有一个容量有限的背包(比如能装10公斤的东西)#xff0c;现在有价值不同#xff0c;重量也不同的几件物品#xff0c;我们要怎样装才能让这个背包尽可能的装的价值最高 这就是为什么这个问题叫01背包问题#xff0c;每个物品只有两种状态,放入…动态规划:01背包问题情景现在有一个容量有限的背包(比如能装10公斤的东西)现在有价值不同重量也不同的几件物品我们要怎样装才能让这个背包尽可能的装的价值最高这就是为什么这个问题叫01背包问题每个物品只有两种状态,放入(1)和不放入(0)问题有一个背包最大承重W10。有4件物品物品1重量2价值3物品2重量3价值4物品3重量4价值5物品4重量5价值6问题选择哪些物品放入背包使总价值最大且总重量≤10普通解法暴力计算我们如果想把每个组合都试一遍总能试出答案#includeiostream#includevector#includealgorithmusingnamespacestd;intbruteForce01(vectorintvalues,vectorintweights,intcapacity){intnvalues.size();intmaxVal0;for(intmask0;mask(1n);mask){intcurWeight0,curValue0;for(inti0;in;i){if(mask(1i)){curWeightweights[i];curValuevalues[i];}}if(curWeightcapacity){maxValmax(maxVal,curValue);}}returnmaxVal;}intmain(){vectorintvalues{3,4,5,6};vectorintweights{2,3,4,5};intcapacity10;cout暴力解法结果: bruteForce01(values,weights,capacity)endl;return0;}确实算出了结果但这个方法非常非常的麻烦n 4的情况下用了16种方法才试出答案时间复杂度时O(n^2)递归#includeiostream#includevector#includealgorithmusingnamespacestd;intknapsackRecursive(inti,intremaining,vectorintvalues,vectorintweights){if(ivalues.size())return0;intnotTakeknapsackRecursive(i1,remaining,values,weights);inttake0;if(remainingweights[i]){takeknapsackRecursive(i1,remaining-weights[i],values,weights)values[i];}returnmax(notTake,take);}intmain(){vectorintvalues{3,4,5,6};vectorintweights{2,3,4,5};intcapacity10;cout递归解法结果: knapsackRecursive(0,capacity,values,weights)endl;return0;}递归解法将这个二问题拆成小问题来解决将选取这个物品和不选这个物品作比较取最大值这个解法看似没有暴力计算这么麻烦但是在计算的过程中会有重叠子问题重复的计算还是会带来效率的低下那么为了避免重叠子问题我们要使用动态规划动态规划二维数组#includeiostream#includevector#includealgorithmusingnamespacestd;intknapsackDP(vectorintvalues,vectorintweights,intcapacity){intnvalues.size();vectorvectorintdp(n1,vectorint(capacity1,0));for(inti1;in;i){intweightweights[i-1];intvaluevalues[i-1];for(intw0;wcapacity;w){if(wweight){dp[i][w]dp[i-1][w];}else{dp[i][w]max(dp[i-1][w],dp[i-1][w-weight]value);}}}returndp[n][capacity];}intmain(){vectorintvalues{3,4,5,6};vectorintweights{2,3,4,5};intcapacity10;coutknapsackDP(values,weights,capacity)endl;return0;}我们创建了一个二维的数组行代表考虑前i个物品列代表背包当前的容量两者合起来就是在考虑前i个物品时背包容量为w时的最大值现在将它初始化现在对前k个物品进行外层遍历在对背包的容量进行内层遍历对于每个dp[i][w]我们都有两种情况装的下和装不下装不下那只能不选了重在在于这个装的下在这个时候我们会有两种选择装和不装这时候就要比较不装的时候和腾出该空间后剩下的价值比较所以同样是比较动态规划只需要计算一遍即可比递归要快的多一维数组#includeiostream#includevector#includealgorithmusingnamespacestd;intknapsack01_1D(vectorintvalues,vectorintweights,intcapacity){intnvalues.size();vectorintdp(capacity1,0);for(inti0;in;i){for(intwcapacity;wweights[i];w--){dp[w]max(dp[w],dp[w-weights[i]]values[i]);}}returndp[capacity];}intmain(){vectorintvalues{3,4,5,6};vectorintweights{2,3,4,5};intcapacity10;coutknapsack01_1D(values,weights,capacity)endl;return0;}dp[w]代表背包容量为w时的最大价值仍然是熟悉的两层遍历唯一不同的一点就是内层遍历变成了逆序遍历为什么会这样这个数组只有一维有限的空间使得计算时会包含当前的物品如果我们使用正序遍历在dp的计算中会出现重复的计算会存在一个物品被用了两次所以我们使用逆序从大容量向小容量思考在计算dp时保证不含当前物品解法对比表比较维度暴力搜索普通递归动态规划(2D)动态规划(1D)时间复杂度O(2ⁿ)O(2ⁿ)O(n×capacity)O(n×capacity)是否重复计算大量重复检查所有组合大量重复相同状态多次计算无重复无重复计算方向无方向自顶向下自底向上自底向上代码复杂度简单中等中等中等需理解逆序适用数据规模n≤15n≤20大中规模大规模核心优势简单直观思维自然标准模板易理解空间最优速度快总结学习01背包问题更能理解动态规划的本质理解其中空间换时间的思想这篇文章是我之前动态规划的进一步学习也为学习后边其他背包问题做铺垫