首页 > 代码库 > 有两艘船需要装运的n箱货物，第一艘船的载重量是c1，第二艘船的载重量是c2，wi是货箱i的重量，且w1+w2+……+wn<=c1+c2
有两艘船需要装运的n箱货物，第一艘船的载重量是c1，第二艘船的载重量是c2，wi是货箱i的重量，且w1+w2+……+wn<=c1+c2
(1) 问题描述：
有两艘船和需要装运的n个货箱，第一艘船的载重量是c1，第二艘船的载重量是c2,wi是货箱的质量，且w1+w2+...+wn <= c1+c2.
希望确定是否有一种可将所有n个货箱全部装船的方法。若有的话，找出该方法。
(2) 举例描述：
当n=3，c1=c2=50，w=[10,40,40]时，可将货箱1、2装到第一艘船上，货箱3装到第二艘船上。
但是如果w=[20,40,40]，则无法将货箱全部装船。由此可知问题可能有解，可能无解，也可能有多解。
(3) 问题分析
虽然是关于两艘船的问题，其实只讨论一艘船的最大装载问题即可。因为当第一艘船的最大装载为bestw时，
若w1+w2+...+wn-bestw <= c2，则可以确定一种解，否则问题就无解。这样的问题转化为第一艘船的最大装载问题。
(4) 算法设计
转化为一艘船的最优化问题后， 问题的解空间为一个子集树。也就是算法要考虑所有物品取、舍情况的组合，
n个物品的取舍组合共有2的n次方个分支。
1> 和回溯算法的思想一样，用FIFO分支搜索所有的分支，并记录已搜索分支的最优解，搜索完子集树也就找出了问题的解。
2> 要想求出最优解，必须搜索到叶结点，所以要记录数的层次。当层次为n+1时，搜索完全部叶结点，算法结束。
3> 分支搜索过程中活结点的"层"是需要标识的，否则入队后无法识别结点所在的层。每处理完一层让"-1"入队，以此来标识
"层"，并用变量i来记录当前层。
4> 每个活结点要记录当前船的装载量。
代码示例：
1 <?php 2 class Queue 3 { 4 private $queue = array(); 5 6 /** 7 * 入栈 8 */ 9 public function push($val) 10 { 11 array_push($this->queue, $val); 12 } 13 14 /** 15 * 出栈 16 */ 17 public function pop() 18 { 19 $value = array_shift($this->queue); 20 return $value; 21 } 22 23 /** 24 * 判断是否为空栈 25 */ 26 public function is_empty() 27 { 28 if(empty($this->queue)) 29 { 30 return true; 31 } else { 32 return false; 33 } 34 } 35 } 36 37 class BranchLimitFIFOSearch 38 { 39 private $n;//n个货箱 40 private $c1;//第一艘船的载重量 41 private $c2;//第二艘船的载重量 42 private $bestw;//第一艘船的最大载量 43 private $ew = 0;//当前船的装载量 44 private $w;//货箱质量数组 array 45 private $s = 0;//所有货箱的重量之后 46 private $queue;//FIFO队列 47 48 /** 49 * 构造函数 50 */ 51 public function __construct($n, $c1, $c2, $w) 52 { 53 $this->n = $n; 54 $this->c1 = $c1; 55 $this->c2 = $c2; 56 $this->w = $w; 57 $this->s = is_array($w) ? array_sum($w) : 0; 58 $this->queue = new Queue(); 59 } 60 61 /** 62 * 最忧装载值 63 * @param $c 第一艘船的载重量 64 */ 65 public function max_loading($c) 66 { 67 $i = 1;//E-节点的层 68 $this->ew = 0;//当前船的装载量 69 $this->bestw = 0;//目前的最优值 70 $this->queue->push(-1); 71 72 while(!$this->queue->is_empty())//搜索子集空间树 73 { 74 if($this->ew + $this->w[$i] <= $c)//检查E-节点的左孩子，货箱i是否可以装载 75 { 76 $this->add_live_node($this->ew + $this->w[$i], $i);//货箱i可以装载 77 } 78 $this->add_live_node($this->ew, $i); 79 80 $this->ew = $this->queue->pop();//取下一个节点 81 82 if(-1 == $this->ew) 83 { 84 if($this->queue->is_empty()) 85 { 86 break; 87 } 88 $this->queue->push(-1); 89 $this->ew = $this->queue->pop();//取下一个节点 90 $i++; 91 } 92 } 93 94 return $this->bestw; 95 } 96 97 /** 98 * 入队 99 */ 100 public function add_live_node($wt, $i) 101 { 102 if($this->n == $i)//是叶子 103 { 104 $this->bestw < $wt && $this->bestw = $wt; 105 } else {//不是叶子 106 $this->queue->push($wt); 107 } 108 } 109 110 /** 111 * 所有货箱的重量 112 */ 113 public function get_s() 114 { 115 return $this->s; 116 } 117 118 /** 119 * 获取最优值 120 */ 121 public function get_bestw() 122 { 123 return $this->bestw; 124 } 125 } 126 127 function branch_limit_FIFO_search() 128 { 129 $n = 3; 130 $c1 = 50; 131 $c2 = 50; 132 $w = array(0,10,40,40); 133 $bfis = new BranchLimitFIFOSearch($n, $c1, $c2, $w); 134 $s = $bfis->get_s();//所有货箱的重量之后 135 136 if($s<=$c1 || $s<=$c2) 137 { 138 die("need only one ship!"); 139 } 140 if($s > $c1+$c2) 141 { 142 die("no solution!"); 143 } 144 145 $bfis->max_loading($c1); 146 $bestw = $bfis->get_bestw(); 147 if($s-$bestw <= $c2) 148 { 149 echo "The first ship loading " . $bestw . "<br/>"; 150 echo "The second ship loading " . ($s - $bestw); 151 } else { 152 echo "no solution!!!"; 153 } 154 } 155 156 branch_limit_FIFO_search();
有两艘船需要装运的n箱货物，第一艘船的载重量是c1，第二艘船的载重量是c2，wi是货箱i的重量，且w1+w2+……+wn<=c1+c2