5.座位调整 百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，效率会大大提高。因此，百度决定进行一次员工座位的大调整。调整的方法如下：1．首先将办公区按照各种零食的摆放分成N个不同的区域（例如：可乐区，饼干区，牛奶区等等）；2．每个员工对不同的零食区域有不同的喜好程度（喜好程度是1~100的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）；3．由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案使得总的喜好程度最大。输入要求：文件第一行包含两个整数N，M(N>=1，M<=300)。分别表示N个区域和M个员工；第二行是N个整数构成的数列a，其中a[i]表示第i个区域可以容纳的员工数(1<=a[i]<=M，a[1]+a[2]+...+a[N]=M)；紧接着是一个M*N的矩阵P，P(i,j)表示第i个员工对第j个区域的喜好程度。例：3 31 1 1100 50 25100 50 25100 50 25输出要求：对于每个测试数据，输出可以达到的最大的喜好程度。例：175数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为100+50+25=175
php求解过程：时间有些长，我用的是4个区的$quarr=array(2,1,1,1);里面1区是2个人容量，加大了数据量，同时运行时间被加大；4个区 5个人，测试出所有的组合，并按和的大小由小到大排序数组，本例运行时间不超过1分钟，可以得到结果
基本方法：生成所有组合，有2个步骤：1取人,2取区（把取到得人放至的区）；取人：一共取人的总数（路8人）次，可以取完一组，假想每次这8人每次都有可能在某次被取，那摩 就要判断已经取的人，然后舍去一区的人，取本组链上新的，得到新的链：0->0|1->0|2->1|3->2（说明：0->0 前面代表取到得人id，后面代表人放置的区id，|是每次的分割0->0|1->0|2->1|付），在取得人要放置区时，通过记录的本组的各区的已有人数，路过要加入某区会超量，不加入，否 这个区可以加入，生成新链（步揍链0->0|1->0|2->1|，记录各区已有人数的链2|1|1，组合为本组的状态链），在这之前需要判断由于排列产生的重复组合，在生成新连前，和已经生成的同级连做比较。通过看2个链能否通过移位达到相同，可以，则舍弃，否 加入，这样避免了排列的树形大范围扩展，直接得到组合形式的链
最后：根据各个组合，得到对应和，由大到小排序
以下是php代码，许多初始量已经设置了，数据生成很多，我没有详细比较，总体看是可以的，可能会有某些错误，在所难免，欢迎各位指出问题
<?phpset_time_limit(0);//座位调整$quarr=array(2,1,1,1);//4个区，值---对应每个区的容量$xihao=array(0=>array(100,20,50,60),1=>array(20,30,50,90),2=>array(60,30,70,100),3=>array(40,30,80,90),4=>array(20,20,50,30));//喜好数组，键代表人//( [0] => 310 [1] => 0->0|1->1|2->3|3->2 $ren=array();$num=count($xihao);//$num=4;for($i=0;$i<$num;$i++)$ren[]=$i;//装载人id 0------num-1
//需要一个表示人入区状态的链条：甲--》区1|乙--》区2；能够表示当前链条中各区人数的链条0|0|0|0; 2者#连接$lian1='';$lian2='';for($i=0;$i<count($quarr);$i++){if($i==0)$lian2.='0';
else $lian2.='|0';
}$lian=$lian1.'#'.$lian2;$lianarr=array($lian);
//while$jishu=1;while($jishu<=count($ren)){//模拟取人，取区的过程$newlianarr=array();for($i=0;$i<count($lianarr);$i++){
$lian=$lianarr[$i];$arr=explode('#',$lian);$lian1=$arr[0];$lian2=$arr[1];$lian1arr=explode('|',$lian1);$lian2arr=explode('|',$lian2);for($i1=0;$i1<count($ren);$i1++){//取人if($lian1!=''){$isyou=0;for($i2=0;$i2<count($lian1arr);$i2++){$t=explode('->',$lian1arr[$i2]);if($ren[$i1]==$t[0]){$isyou=1;break;}
}//end for($i2=0;$i2 判断是否已取过的人
if($isyou==1)continue;//已取过的人,不取
}$quren=$ren[$i1];//欲取的人
//讨论取的人放置的区，理想可以放置所有的区，需要判断是否加入后是否会超过该区的容量，是-舍去，否--加入for($i3=0;$i3<count($quarr);$i3++){$t=$lian2arr;if(($lian2arr[$i3]+1)>$quarr[$i3])continue;//当加入新人会超量时，不加入该区if($lian1=='')$newlian1=$quren.'->'.$i3;else $newlian1=$lian1.'|'.$quren.'->'.$i3;$t[$i3]++;$newlian2=implode('|',$t);$newlian=$newlian1.'#'.$newlian2;
//进一步校验，过滤重复的，指是否 人-》区只是位置有变化$t1=explode('|',$newlian1);$shequ=0;
for($i4=0;$i4<count($newlianarr);$i4++){$t2=explode('#',$newlianarr[$i4]);$t3=explode('|',$t2[0]);$keyishu=0;for($i5=0;$i5<count($t1);$i5++){$keyi=0;for($i6=$i5;$i6<count($t3);$i6++){if(trim($t3[$i6])==trim($t1[$i5])){$keyi=1;$temp=$t3[$i6];$t3[$i6]=$t3[$i5];$t3[$i5]=$temp;break;}
}//end for($i6=$i5;$if($keyi==1)$keyishu++;else break;}//end for($i5=0;//echo $keyishu.'-'.count($t1).'<br>';if($keyishu==count($t1)){$shequ=1;break;}}//end for($i4=0;//echo $shequ;if($shequ==1)continue;
$newlianarr[]=$newlian;}//end for($i3=0;
}//end for($i1=0;
}//end for($i=0;$i<count($lianarr)
$lianarr=$newlianarr;$jishu++;}
//打印得到的所有组合，已经去重echo '得到的所有组合（说明：[0] => 0->0|1->1|2->2|3->3#1|1|1|1---#号前是组合，#号后是处理时的组合对应每个区数量标志，起辅助作用，最后应该都是满的）<br><br>';print_r($lianarr);echo '<br><br><br>';
//获得最大喜好，生成每种组合的喜好，排序$qiuhe=array();//生成对应的和for($i=0;$i<count($lianarr);$i++){$lianstr=$lianarr[$i];$strarr=explode('#',$lianstr);$str1=$strarr[0];$he=0;$temparr=explode('|',$str1);for($i1=0;$i1<count($temparr);$i1++){$t=explode('->',$temparr[$i1]);$hang=$t[0];$lie=$t[1];$he=$he+$xihao[$hang][$lie];}//end for($i1=0;$qiuhe[]=array($he,$str1);
}
//根据和排序，由大到小for($i=0;$i<count($qiuhe);$i++){$max=$qiuhe[$i][0];for($j=$i;$j<count($qiuhe);$j++){if($qiuhe[$j][0]>$max){$max=$qiuhe[$j][0];$t=$qiuhe[$j];$qiuhe[$j]=$qiuhe[$i];$qiuhe[$i]=$t;}}}
//打印数据：和--对应的组合echo '所有组合根据和由大到小排序后的数组：（ 说明：[0] => 310---和 ；[1] => 0->0|1->1|2->3|3->2---组合）<br><br>';print_r($qiuhe);
?>
