制作网站吗,myeclipse做网站的步骤,江阴网站优化,东莞阿里巴巴网站建设(1)0-1背包问题思路#xff1a;构造一个二叉树#xff0c;每个商品都有两种状态#xff0c;要或者不要。如果要就在这个节点的左枝挂子节点#xff0c;如果不要就在右节点挂子节点。如果全部商品都分配完状态之后就回溯#xff0c;回溯到一个还有其他选择的节点#xff0…(1)0-1背包问题思路构造一个二叉树每个商品都有两种状态要或者不要。如果要就在这个节点的左枝挂子节点如果不要就在右节点挂子节点。如果全部商品都分配完状态之后就回溯回溯到一个还有其他选择的节点接着往这个选择发展节点然后再回溯然后再往下。。。。 直到无路可走就结束了。假如限制重量是10总共有四个商品重量分别是2, 5, 4, 2 价格分别是6, 3, 5, 4。第一轮的路程如5-11图第1个商品要第2个商品要第3个商品发现装不下了所以到第3个节点只能走右节点并且第3个节点的左节点成为死节点没有发展下去的可能了。第4个商品要此时已经给所有的商品赋予状态了(要或者不要)记录下此时所有商品的价值和记为最优价格。接着就开始回溯如5-13从节点5先是回溯到节点4(此时购物车有123选择不要4肯定是要的所以没必要再发展4节点的右节点)再到节点3(节点三的左节点是死节点)再到节点2节点2的右节点是可选的然后接着按照刚开始的逻辑接着往下走就可以了等继续走完这一轮计算最优值更新下最优值然后再回溯。。。剪枝如果按照上面的逻辑其实几乎相当于遍历了所有的可能性。如果有4个商品就会有2的4次方种可能有些不可能是最优结果的分支直接就剪掉就可以了比如如果按照上面的逻辑是会有1不要2不要3不要4不要这个分支。所以如果发现背包可以把剩下的商品都装入的情况就直接给剩余的商品赋值为要就可以了。当1不要2不要的时候3和4可以都装入背包直接都要就可以了。没必要再走3不要的分支(直接设置成死节点)。或者也可以判断就算把剩余的都加进包里总价值也小于当前最优值当前这条路也没必要走了。 代码1 ?php2 $w [2, 5, 4, 2];3 $v [6, 3, 5, 4];4 $current getNode(0);5 $count count($w);6 list($limit, $best, $cw, $cp, $bestMap, $map) [10, 0, 0, 0, array(), array()];7 $noBack true;89 while (1) {10 $node getNode($current-level 1, $current);11 if ($current-level $count $noBack) {12 if ($best array_sum(array_slice($v, $current-level)) $cp) {13 $current-l false; //剪枝14 $current-r false;15 $noBack false;16 } elseif (is_object($current-l)|| $current-l false) {17 $node-dir 0; //这种情况是回溯回来的直接发展右节点就可以了18 $current-r $node;19 } elseif ($cw $w[$current-level] $limit) {20 $cw $w[$current-level]; $cp $v[$current-level];21 $node-dir 1; //1代表左枝0代表右枝22 $current-l $node; //这种情况代表背包可以装下所以挂在左节点23 $map[$current-level] 1;24 } else{25 $node-dir 0;26 $current-r $node;27 $current-l false; //这种情况代表装不下左节点是死节点发展右节点28 }29 $current $node;30 } else { //走完一轮开始回溯31 if ($cp $best) { //记录最优值32 $best $cp; $bestMap $map;33 }34 while (1) { //开始回溯35 $deal isset($current-dir) ? $current-dir : 0;36 $current $current-p;37 if ($current null) {38 break 2; //到头了,结束39 }40 if (isset($map[$current-level])) {41 unset($map[$current-level]);42 $cw - $w[$current-level] * $deal; //怎么加的怎么减回去43 $cp - $v[$current-level] * $deal;44 }45 if ($current-l null || $current-r null) { //存在活结点46 $noBack true;47 break;48 }49 }50 }51 unset($node);52 }5354 function getNode($level, $p null) {55 $node newstdClass();56 $node-level $level; $node-p $p;57 $node-l null; $node-r null;58 return $node;59 }6061 print_r([‘map‘ $bestMap, ‘val‘ $best]);原文https://www.cnblogs.com/wangjianheng/p/11857435.html
