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

php  /  管理员 发布于 7年前   169

本文实例讲述了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 '
';  }}//按照价格和重量比排序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写杨辉三角实例代码
• 深入理解PHP几个算法:PHP冒泡、PHP二分法、PHP求素数、PHP乘法表
• PHP求最大子序列和的算法实现
• php 3行代码的分页算法(求起始页和结束页)
• php实现猴子选大王问题算法实例
• php约瑟夫问题解决关于处死犯人的算法
• PHP基于回溯算法解决n皇后问题的方法示例
• PHP使用栈解决约瑟夫环问题算法示例
• PHP基于递归算法解决兔子生兔子问题
• PHP实现的解汉诺塔问题算法示例
• PHP实现的杨辉三角求解算法分析