贪心算法

所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅仅是在某种意义上的局部最优解。

贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性（即某个状态以后的过程不会影响以前的状态，只与当前状态有关。）

所以，对所采用的贪心策略一定要仔细分析其是否满足无后效性。比如，求最小生成树的Prim算法和Kruskal算法都是漂亮的贪心算法。

有6个大小不一的东西，要装固定的100体积盒子里面，最少需要几个盒子？[不是最优解]

<?php
$items[0] = 60;
$items[1] = 45;
$items[2] = 35;
$items[3] = 20;
$items[4] = 20;
$items[5] = 20;
echo "<pre>";
$aa = greedy($items, 100);
print_r($aa);
 
/*
* 贪婪算法
* $arr      array   处理数组
* $volume   int     盒子容量
*/
function greedy($arr, $volume)
{
    $box = array();
    $boxNum = 0;
    $num = count($arr);
    for ($i = 0; $i < $num; $i++) {
        $boxCode = true;
        for ($j = 0; $j < $boxNum; $j++) {
            if ($arr[$i] + $box[$j]['v'] <= $volume) {
                $box[$j]['v'] += $arr[$i];
                $box[$j]['k'][] = $i;
                $boxCode = false;
                break;
            }
        }
        if ($boxCode) {
            $box[$boxNum]['v'] = $arr[$i];
            $box[$boxNum]['k'][] = $i;
            $boxNum++;
        }
    }
 
    return $box;
}

1.什么叫01背包问题？

背包问题通俗的说，就是假如你面前有5块宝石分别为a, b, c, d, e，每块宝石的重量不同，并且每块宝石所带来的价值也不同（注意：这里宝石的重量的价值没有特定关系），目前我们有一个背包，只有固定的容量，要解决的问题就是在一定容量的背包面前装哪几块宝石才能获取到最大的价值，对于每块宝石我们只有拿或者不拿这两种选择，拿为1不拿为0，因此叫做0-1背包问题，下面通过一个例子来深入理解背包问题

2.01背包问题例子

假设a, b, c, d, e五块宝石的重量分别为为2， 2， 6， 5， 4，价值分别为6， 3， 5，4， 6 ，我们目前的背包可以装重量为10的物品，怎么装才能使得获取的价值最大？

首先对于我们人去操作而言，首先考虑应该是质量最轻，并且价值最大的，从数据中我们可以看到宝石a质量最小，且价值最大，应该优先考虑装这一块，然后依次考虑其他的。这种方式就是考虑性价比最高的宝石。我们可以将这个问题进行简化，目前是背包承重为10，因此我们的选择较多，不知从何下手，那么我们假设背包的承重为5或者是3甚至是2， 1。在这种情况下，我们的选择就不多了，对于人类选择也是，在选择不多的情况下更容易找出最优方案，同样计算机也是。因此我们的背包问题也是从这开始，将选择较多的问题转化为选择不多的问题。在选择不多的情况下进行选择，有利于比较判断，依次递增，最后解决背包承重为10的问题。

对于背包问题，其实是一个动态规划，对于动态规划，大多数都是用一个数组来进行保存，对于初学者而言，如果我直接给你个数组公式，相信你看着也不太懂公式表示什么，数组怎么来的，别着急，耐心看，下面就一步一步的解释该数组的数据是怎么来的，公式是怎么推导出来的，附代码

//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 '<br>';
  }
}
//按照价格和重量比排序
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 '0-1背包最优解为:';
echo tanxin($x);