The principle and usage of PHP greedy algorithm

This article mainly introduces the PHP greedy algorithm to solve the 0-1 knapsack problem. The example analyzes the principle of the greedy algorithm and the implementation skills of the knapsack problem. Friends in need can refer to the following

The examples of this article describe PHP The greedy algorithm solves the 0-1 knapsack problem. Share it with everyone for your reference. The specific analysis is as follows:

The greedy algorithm solves the 0-1 knapsack problem, and the global optimal solution is obtained through the local optimal solution! More flexible than dynamic programming to solve the knapsack problem!

//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,&#39; &#39;,$val->price;
    echo &#39;<br>&#39;;
  }
}
//按照价格和重量比排序
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 &#39;0-1背包最优解为:&#39;;
echo tanxin($x);

Summary: The above is the entire content of this article, I hope it will be helpful to everyone's study.

Related recommendations:

php method of recursive function traversal and deletion of files

php method of subtracting two arrays

php method to calculate the accurate date of Easter

The above is the detailed content of The principle and usage of PHP greedy algorithm. For more information, please follow other related articles on the PHP Chinese website!