首页 / 网页编程 / PHP / PHP贪婪算法解决0-1背包问题实例分析

//0-1背包贪心算法问题class tanxin{public $weight;public $price;public function __construct（$weight=0,$price=0）{$this->weight=$weight;$this->price=$price;}}//生成数据$n=10;for（$i=1;$i<=$n;$i++）{$weight=rand（1,20）;$price=rand（1,10）;$x[$i]=new tanxin（$weight,$price）;}//输出结果function display（$x）{$len=count（$x）;foreach（$x as $val）{echo $val->weight," ",$val->price;echo "<br>";}}//按照价格和重量比排序function tsort（&$x）{$len=count（$x）;for（$i=1;$i<=$len;$i++）{for（$j=1;$j<=$len-$i;$j++）{ $temp=$x[$j];$res=$x[$j+1]->price/$x[$j+1]->weight;$temres=$temp->price/$temp->weight;if（$res>$temres）{$x[$j]=$x[$j+1];$x[$j+1]=$temp;}}} }//贪心算法function tanxin（$x,$totalweight=50）{$len=count（$x）;$allprice=0;for（$i=1;$i<=$len;$i++）{if（$x[$i]->weight>$totalweight） break;else{$allprice+=$x[$i]->price;$totalweight=$totalweight-$x[$i]->weight;}}if（$i<$len） $allprice+=$x[$i]->price*（$totalweight/$x[$i]->weight）;return $allprice;}tsort（$x）;//按非递增次序排序display（$x）;//显示echo "0-1背包最优解为:";echo tanxin（$x）;