/**
 * PHP贪婪算法解决0-1背包问题代码
 *
 * @param 
 * @arrange 512-笔记网： jb51.cc
 **/
//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);
/***   来自编程之家 jb51.cc（jb51.cc）   ***/