背包算法（phpchina编程大赛第7题原创）

设有n 种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n 种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M，而价值的和为最大。
new code7();
class code7{
    private $GoodsNum = 10;                                  //允许的物品类型数量
    private $GoodsMax = "";                                  //背包允许最大重量
    private $GoodsArr = "";                                  //物品数组
   
    //构造函数
    public function __construct(){
        $this->GoodsMax = rand(5*$this->GoodsNum,50*$this->GoodsNum);
        $this->GoodsArr = $this->GoodsArr($this->GoodsNum);
        print_r($this->GoodsArr);
        usort($this->GoodsArr, array("code7", "Compare"));        //数组按'单位重量的最大价值'排序
        $arrT = $this->GetGoods($this->GoodsMax,$this->GoodsArr);
        print_r($arrT);
    }
   
    //构造物品数组
    private function GoodsArr($GoodsNum){
        $Goods    = array();
        for($i=0;$i<$GoodsNum;$i++){                        //初始化每个物品类型的重量和价值
            $Goods[$i][0]="G".$i;                           //名称
            $Goods[$i][1]=rand(50,80);                      //重量
            $Goods[$i][2]=rand(20,50);                      //价值
            $Goods[$i][3]=$Goods[$i][2]/$Goods[$i][1];      //单位重量的最大价值
        }
        return $Goods;
    }
   
    private function GetGoods($GoodsMax,$GoodsArr){
        //最大单位物品的重量、价值、数量
        $Goods_w      = 0;
        $Goods_v      = 0;
        $Goods_n      =array();
        //当前空间的允许物品最大价值
        $Goods_weight = 0;
        $Goods_value  = 0;
        $Goods_num    =array();
       
        $GoodsArrT = array_shift($GoodsArr);                              //去除'单位重量的最大价值'最大的物品
        $num       = floor(($GoodsMax-$Goods_weight)/$GoodsArrT[1]);      //最大单位物品的最大允许个数
        if(count($GoodsArrT)==0 || $GoodsMax-$Goods_w == $GoodsArrT[1]*$num){
            if($num>0){
                $Goods_weight += $GoodsArrT[1]*$num;
                $Goods_value  += $GoodsArrT[2]*$num;
                $Goods_num[$GoodsArrT[0]] = $num;
            }
        }else{
            for($i=0;$i<=$num;$i++){                                                    //计算最大单位物品不同数量时的最大价值
                $Goods_w = $GoodsArrT[1]*$i;
                $Goods_v = $GoodsArrT[2]*$i;
                $Goods_n[$GoodsArrT[0]] = $i;
                if(($num-$i)*$GoodsArrT[2]/($GoodsMax-$Goods_w) < $GoodsArrT[0][3]){    //剩余空间的单位价值小于下件物品的单位价值
                    list($subuse_w,$subuse_v,$subusewp)=$this->GetGoods($GoodsMax-$Goods_w,$GoodsArr);
                } else {
                    $subuse_w = 0;
                    $subuse_v = 0;
                    $subusewp =array();
                }
                if($Goods_w+$subuse_v > $Goods_value || $Goods_value==0){               //比较最大价值
                    $Goods_weight = $Goods_w+$subuse_w;
                    $Goods_value  = $Goods_v+$subuse_v;
                    if($i>0){
                        $Goods_num = array_merge($Goods_n,$subusewp);
                    } else{
                        $Goods_num = $subusewp;
                    }
                }
            }
        }
        //返回 使用的重量，最大价值、使用的物品数量数组
        return array($Goods_weight,$Goods_value, $Goods_num);
       
    }
   
    //比较函数
    public static function Compare($a, $b){
        if ($a[3] == $b[3]) {
            return 0;
        }
        return ($a[3] > $a[3]) ? +1 : -1;
    }
}