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

            本文实例讲述了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;$iweight,' ',$val->price;
    echo '
';
  }
}
//按照价格和重量比排序
function tsort(&$x)
{
  $len=count($x);
  for($i=1;$iprice/$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;$iweight>$totalweight) break;
    else{
      $allprice+=$x[$i]->price;
      $totalweight=$totalweight-$x[$i]->weight;
    }
  }
  if($iprice*($totalweight/$x[$i]->weight);
  return $allprice;
}
tsort($x);//按非递增次序排序
display($x);//显示
echo '0-1背包最优解为:';
echo tanxin($x);
希望本文所述对大家的php程序设计有所帮助。
            
            
您可能感兴趣的文章:

php约瑟夫问题解决关于处死犯人的算法

php实现猴子选大王问题算法实例

PHP基于递归实现的约瑟夫环算法示例

PHP使用栈解决约瑟夫环问题算法示例

PHP实现的贪婪算法实例

php实现的生成迷宫与迷宫寻址算法完整实例

PHP基于回溯算法解决n皇后问题的方法示例

PHP实现图的邻接矩阵表示及几种简单遍历算法分析

PHP递归实现汉诺塔问题的方法示例