PHP 탐욕 알고리즘의 원리와 사용법

이 글에서는 주로 0-1 배낭 문제를 해결하기 위한 PHP 탐욕 알고리즘을 소개합니다. 이 예제에서는 탐욕 알고리즘의 원리와 배낭 문제의 구현 기술을 분석합니다. 배낭 문제에 대한 방법으로 0-1 문제를 해결하도록 PHP 탐욕 알고리즘을 알려줍니다. 참고할 수 있도록 모든 사람과 공유하세요. 구체적인 분석은 다음과 같습니다.

그리디 알고리즘은 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,&#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);

요약

: 위 내용은 이 글의 전체 내용입니다. 모든 분들의 공부에 도움이 되었으면 좋겠습니다. 관련 권장 사항:

PHP 재귀 함수로 파일을 탐색하고 삭제하는 방법

두 배열을 빼는 PHP 방법

부활절의 정확한 날짜를 계산하는 PHP 방법

위 내용은 PHP 탐욕 알고리즘의 원리와 사용법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!