Le principe et l'utilisation de l'algorithme gourmand PHP

Cet article présente principalement l'algorithme glouton PHP pour résoudre le problème du sac à dos 0-1. Il analyse les principes de l'algorithme glouton et les compétences de mise en œuvre du problème du sac à dos avec des exemples. Les amis dans le besoin peuvent s'y référer

<.>Cet article décrit les exemples de PHP L'algorithme glouton résout le problème du sac à dos 0-1. Partagez-le avec tout le monde pour votre référence. L'analyse spécifique est la suivante :

L'algorithme glouton résout le problème du sac à dos 0-1, et la solution optimale globale est obtenue grâce à la solution optimale locale ! Plus flexible que la programmation dynamique pour résoudre le problème du sac à dos !

//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);

Résumé : Ce qui précède est l'intégralité du contenu de cet article, j'espère qu'il sera utile à l'étude de chacun.

Recommandations associées :

Comment parcourir et supprimer des fichiers à l'aide de la fonction récursive de php

Comment soustraire deux tableaux en php

Méthode php pour calculer la date précise de Pâques

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!