dw怎么导入网站模板如何开一家外贸网店

dw怎么导入网站模板,如何开一家外贸网店,vs2017 做c 网站,百度 网站改版了0-1背包问题输入#xff1a;给定物品集合 #xff0c;每个物品 i 对应重量 和价值#xff1b;同时给定背包的总重量限制 W。输出#xff1a;选择物品的一个子集#xff0c;满足 “子集总重量不超过 W” 的约束#xff0c;同时最大化子集的总价值。这是一个二元决策问题给定物品集合每个物品 i 对应重量和价值同时给定背包的总重量限制 W。输出选择物品的一个子集满足 “子集总重量不超过 W” 的约束同时最大化子集的总价值。这是一个二元决策问题简单来说需要在一个有限容量的背包中放入尽可能高价值的物品对于每个可选物品只有放入\不放入两种状态。相较于分数背包问题即非二元决策如某个物品可以选择放入一半0-1背包问题无法通过贪心的思想来解决比如下例背包的重量限制为 15kg待选物品的属性价值、重量、单位价值如下如果按照贪心的思路即选择单位价值更高的物品步骤如下优先选单位价值最高的物品 19kg10$背包剩余重量15-96kg物品 212kg超过剩余重量不选选次高单位价值的物品 32kg1$背包剩余重量6-24kg物品 47kg、物品 55kg均超过剩余重量不选最终选择 “物品 1 物品 3”总价值 11$总重量 11kg。但若选择 “物品 1 物品 5”总重量为9514kg不超过限制总价值为10212美元明显高于贪心方法得到的 11 美元。这一缺陷的根源是0-1 背包的 “物品不可拆分” 约束使得贪心算法无法灵活调整物品组合因此必须通过动态规划等方法枚举所有合法组合的价值才能得到真正的最优解。寻找最优子结构我们可以将 0-1 背包的求解过程转化为每个物品是否选择的多阶段决策每个决策阶段对应一个物品例如第i阶段决定 “是否选择物品i”所有阶段的决策组合选 / 不选的集合对应最终的物品子集。以 “是否选择最后一个物品n” 作为首个决策假设物品按顺序排列从后往前分析该决策包含两种互斥选项每种选项对应一个子问题选项 1选择物品n约束变为 “背包剩余重量为”需从物品中选择子集最大化总价值此时总价值需加上物品n的价值。选项 2不选择物品n约束保持 “背包重量限制为W”需从物品中选择子集最大化总价值。因此原问题物品、重量限制的最优解可通过 “是否选择物品n” 的决策转化为两个子问题的最优解的最大值下面以物品信息背包重量限制展示一下算法过程目标设置 “无物品i0” 时的所有子问题解。逻辑当没有物品可选时任何重量限制下的总价值都是 0因此OPT[0, w] 0w从 0 到 6。目标计算 “前 1 个物品、重量限制的最大价值。逻辑第 1 个物品重量仅当时可选择取最大值 2填充OPT[1,2]为 2。目标计算 “前 2 个物品、重量限制的最大价值。逻辑第 2 个物品重量需基于前 1 个物品的解计算取最大值 4填充OPT[2,4]为 4。目标计算 “前 3 个物品、重量限制的最大价值。逻辑第 3 个物品重量需基于前 2 个物品的解计算取最大值 3填充OPT[3,3]为 3。最终可通过OPT[3,6]得到原问题的最优价值。算法总结如下用二维数组OPT[i, w]简化表示子问题OPT({1,2,...,i}, w)即前i个物品在重量限制w下的最大价值。之后按状态转移方程来进行即可。回溯步骤 1回溯原问题 OPT[3,6]前 3 个物品、重量 6计算逻辑OPT[3,6] max(OPT[2,6]4, OPT[2, 6-3] v_3OPT[2,3]3235)最终值为 5。决策因OPT[3,6] OPT[2,3] v_3说明选择了物品 3后续回溯到OPT[2,3]前 2 个物品、重量6-33。步骤 2回溯子问题 OPT[2,3]前 2 个物品、重量 3计算逻辑OPT[2,3] max(OPT[1,3]2, OPT[1, 3-2] v_2OPT[1,1]2022)最终值为 2。决策因OPT[2,3] OPT[1,1] v_2说明选择了物品 2后续回溯到OPT[1,1]前 1 个物品、重量3-21。步骤 3回溯子问题 OPT[1,1]前 1 个物品、重量 1因物品 1 的重量w_12 1无法选择故OPT[1,1]0说明未选择物品 1。洛谷上对应的题目对应代码如下#include iostream #include vector #include algorithm using namespace std; int main() { int t, m; cin t m; vectorint time(m1), val(m1); // 草药1~m for (int i1; im; i) { cin time[i] val[i]; } // 定义opt[前i个物品][时间j]初始化为0 vectorvectorint opt(m1, vectorint(t1, 0)); for (int i1; im; i) { // 处理前i个物品 for (int j1; jt; j) { // 处理时间j if (j time[i]) { opt[i][j] opt[i-1][j]; // 装不下不选 } else { // 选/不选的最大值 opt[i][j] max(opt[i-1][j], opt[i-1][j-time[i]] val[i]); } } } cout opt[m][t]; // 前m个物品、时间t的最大价值 return 0; }