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

墨辰丷
Libérer: 2023-03-31 17:50:01
original
1823 Les gens l'ont consulté

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);
Copier après la connexion

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!

Étiquettes associées:
source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal