算法导论第16章 贪心算法-0-1背包问题—动态规划求解

来源:http://www.guanqinbiaoye.com 作者:计算机编程 人气:181 发布时间:2020-02-07
摘要:本文实例讲述了PHP贪婪算法解决0-1背包问题的方法。分享给大家供大家参考。具体分析如下: 1、前言 贪心算法解决0-1背包问题,全局最优解通过局部最优解来获得!比动态规划解决背

本文实例讲述了PHP贪婪算法解决0-1背包问题的方法。分享给大家供大家参考。具体分析如下:

1、前言

贪心算法解决0-1背包问题,全局最优解通过局部最优解来获得!比动态规划解决背包问题更灵活!

  前段时间忙着搞毕业论文,看书效率不高,导致博客一个多月没有更新了。前段时间真是有些堕落啊,混日子的感觉,很少不爽。今天开始继续看算法导论。今天继续学习动态规划和贪心算法。首先简单的介绍一下动态规划与贪心算法的各自特点及其区别。然后针对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;$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,' ',$val->price;
    echo '
';
  }
}
//按照价格和重量比排序
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($iprice*($totalweight/$x[$i]->weight);
  return $allprice;
}
tsort($x);//按非递增次序排序
display($x);//显示
echo '0-1背包最优解为:';
echo tanxin($x);

2、动态规划与贪心算法

希望本文所述对大家的php程序设计有所帮助。

  关于动态规划的总结请参考。这里重点介绍一下贪心算法的过程。贪心算法是通过一系列的选择来给出某一个问题的最优解,每次选择一个当前(看起来是)最佳的选择。贪心算法解决问题的步骤为:

(1)决定问题的最优子结构

(2)设计出一个递归解

威尼斯网站,(3)证明在递归的任一阶段,最优选择之一总是贪心选择。保证贪心选择总是安全的。

(4)证明通过贪心选择,所有子问题(除一个意外)都为空。

(5)设计出一个实现贪心策略的递归算法。

(6)将递归算法转换成迭代算法。

  什么时候才能使用贪心算法的呢?书中给出了贪心算法的两个性质,只有最优化问题满足这些性质,就可采用贪心算法解决问题。

威尼斯游戏网站,(1)贪心选择性质:一个全局最优解可以通过举办最优解(贪心)选择来达到。即:当考虑做选择时,只考虑对当前问题最佳的选择而不考虑子问题的结果。而在动态规划中,每一步都要做出选择,这些选择依赖于子问题的解。动态规划一般是自底向上,从小问题到大问题。贪心算法通常是自上而下,一个一个地做贪心选择,不断地将给定的问题实例规约为更小的子问题。

(2)最优子结构:问题的一个最优解包含了其子问题的最优解。

动态规划与贪心的区别:

贪心算法: 
(1)贪心算法中,作出的每步贪心决策都无法改变,因为贪心策略是由上一步的最优解推导下一步的最优解,而上一部之前的最优解则不作保留; 
(2)由(1)中的介绍,可以知道贪心法正确的条件是:每一步的最优解一定包含上一步的最优解。 

动态规划算法: 
(1)全局最优解中一定包含某个局部最优解,但不一定包含前一个局部最优解,因此需要记录之前的所有最优解 ;
(2)动态规划的关键是状态转移方程,即如何由以求出的局部最优解来推导全局最优解 ;
(3)边界条件:即最简单的,可以直接得出的局部最优解。

3、0-1背包问题描述

本文由威尼斯游戏网站发布于计算机编程,转载请注明出处:算法导论第16章 贪心算法-0-1背包问题—动态规划求解

关键词:

上一篇:PHP回溯法解决0-1背包问题实例分析

下一篇:没有了

最火资讯