背包问题的PHP算法

8516830

引用

<?php
// http://tieba.baidu.com/f?kz=283979751
/*
设有n 种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n 种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M，而价值的和为最大。
Input
第一行：两个整数，M(背包容量，M<= 200)和N(物品数量，N<= 30)； 第2..N+1 行：每行二个整数Wi,Ui，表示每个物品的重量和价值。
Output
仅一行，一个数，表示最大总价值。
Sample Input
12 4
2  1
3  3
4  5
7  9
Sample Output
15
*/
set_time_limit(30);
define(’NOWTIME’,time());
function microtime_float()
{
    list($usec, $sec) = explode(” “, microtime());
$sec=$sec-NOWTIME;
    return ((float)$usec + (float)$sec);
}
//初始化数组
/*
$bbw=12;
$arywp=array();
$arywp[]=array(’d',2,1);
$arywp[]=array(’c',3,3);
$arywp[]=array(’b',4,5);
$arywp[]=array(’a',7,9);
*/
$time_start = microtime_float();
//开始计算
$wpnum=count($arywp);
$wpnum=20; //允许的物品类型数量
$bbw=rand(5*$wpnum,50*$wpnum); //背包允许最大重量
for($i1=0;$i1<$wpnum;$i1++){ //初始化每个物品类型的重量和价值
$arywp[$i1][0]=”w”.$i1; //名称
$arywp[$i1][1]=rand(50,80); //重量
$arywp[$i1][2]=rand(20,50); //价值
$arywp[$i1][3]=$arywp[$i1][2]/$arywp[$i1][1];//单位重量的最大价值
}
function cmp($a, $b){
$returnvalue=0;
    if ($a[3] == $b[3]) {
  $returnvalue=  0;
    } else {
     $returnvalue = ($a[3] > $b[3]) ? -1 : 1;
}
return $returnvalue;
}
//按单位最大价值排序
usort($arywp, “cmp”);
print_r($arywp);
echo ” <br />\n”;
//递归函数，计算剩余空间的允许物品最大价值
function getmaxval($bbw,$arywp){
//最大单位物品的重量、价值、数量
$use_w=0;
$use_v=0;
$ary_userwp=array();
//当前空间的允许物品最大价值
$maxwgt=0;
$maxval=0;
$maxuserwp=array();

$wp = array_shift($arywp);
$num= floor(($bbw-$use_w)/$wp[1]); //最大单位物品的最大允许个数
//echo ” countmax : $num * “.$wp[0].”<br/>\n”;
if(count($arywp)==0 || $bbw-$use_w==$wp[1]*$num){ //没有剩余物品或刚好填满 //递归结束条件
  if($num>0){
   $maxwgt+=$wp[1]*$num;
   $maxval+=$wp[2]*$num;
   $maxuserwp[$wp[0]]=$num;
  }
} else {
  for($i=0;$i<=$num;$i++){ //计算最大单位物品不同数量时的最大价值
   $use_w=$wp[1]*$i;
   $use_v=$wp[2]*$i;
   $ary_userwp[$wp[0]]=$i;
   if(($num-$i)*$wp[2]/($bbw-$use_w) < $arywp[0][3]){ //剩余空间的单位价值小于下件物品的单位价值
    list($subuse_w,$subuse_v,$subusewp)=getmaxval($bbw-$use_w,$arywp);
   } else {
    $subuse_w=0;
    $subuse_v=0;
    $subusewp=array();
   }
   if($use_v+$subuse_v>$maxval || $maxval==0){ //比较最大价值
    $maxwgt=$use_w+$subuse_w;
    $maxval=$use_v+$subuse_v;
    if($i>0){
     $maxuserwp=array_merge($ary_userwp,$subusewp);
    } else{
     $maxuserwp=$subusewp;
    }
   }
  }
  //print_r($maxuserwp);
  //echo ” maxwgt : $maxwgt  maxval : $maxval<br/>\n”;
}
//返回 使用的重量，最大价值、使用的物品数量数组
return array($maxwgt,$maxval, $maxuserwp);
}
//开始计算
$arysulte= getmaxval($bbw,$arywp);
//输出结果
echo ” bbw “.$bbw.” “;
print_r($arysulte);
$time_end = microtime_float();
$runtime = $time_end – $time_start;
echo ” runtime : “.$runtime;
?>

原文链接http://www.bao00long.cn/2009/package.html