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

yipeiwu_com7年前PHP代码库

本文实例讲述了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 Hash函数,增强密码安全

1.声明 密码学是一个复杂的话题,我也不是这方面的专家。许多高校和研究机构在这方面都有长期的研究。在这篇文章里,我希望尽量使用简单易懂的方式向你展示一种安全存储Web程序密码的方法。 2...

为何说PHP引用是个坑,要慎用

前言 去年我参加了很多次会议,其中八次会议里我进行了相关发言,这其中我多次谈到了 PHP 的引用问题,因为很多人对它的理解有所偏差。在深入讨论这个问题之前,我们先回顾一下引用的基本概念,...

php代码书写习惯优化小结

(1)使用 static 静态方法比普通方法快4倍(2)echo输出快于print(3)连接字符使用 , 代替 .(4)循环之前先取出最大值,而不是在循环里面取值  ...

php数组函数序列之array_slice() - 在数组中根据条件取出一段值,并返回

array_slice()定义和用法 array_slice() 函数在数组中根据条件取出一段值,并返回。 注释:如果数组有字符串键,所返回的数组将保留键名。(参见例子 4) 语法 ar...

php正则删除img标签的方法示例 原创

本文实例讲述了php正则删除img标签的方法。分享给大家供大家参考,具体如下: 一、问题 正则抓取过程中需要删除正文中的img标签,如: <div>欢迎访问【宜配屋www...