PHP贪婪算法解决0-1背包问题实例分析

本文实例讲述了PHP贪婪算法解决0-1背包问题的方法。分享给大家供大家参考。具体分析如下:

贪心算法解决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);

希望本文所述对大家的php程序设计有所帮助。

PHP贪婪算法解决0-1背包问题实例分析

郑重声明:本网站发布的内容(图片、视频和文字)以及用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服

发表评论

登录后才能评论