rucksack.php

<?php
/**
 * http://www.cnblogs.com/fengty90/p/3768845.html
 * 背包问题，动态规划实现
 * 
 * 数据：物品个数n=5,物品重量w[n]={0，2，2，6，5，4},物品价值V[n]={0，6，3，5，4，6},
 *     背包的最大容量为10
 *     
 * 输出整个的矩阵图形，其实只有最后一个既重量为10的列才是最后的结果，其它表格数据都是为了推算上层数据而存在
 * 
 */


//动态规划
$c = 10;//总重量
$ws = [[4,6], [5,4], [6,5], [2,3], [2,6]];  //按照给出物品的数据，相反顺序列出，为了适应表格中的展示顺序
foreach($ws as $r=>$w) {
    $z = $w[0];//重量
    $v = $w[1];//价值
    for($i=0;$i<=10;$i++) {
        if($z > $i) {
            if($r == 0) {
                $row[$r][$i] = [0, 0];
            } else {
                $row[$r][$i] = $row[$r-1][$i];
            }
        } else {
            if($r == 0) {
                $row[$r][$i] = [$v, $r+1];
            } else {
                $n = $row[$r-1][$i][0];//不放入的值
                $y = $v + $row[$r-1][$i-$z][0];//放入的值
                
                if($y > $n) {
                    $row[$r][$i][0] = $y;
                    $row[$r][$i][1] = $row[$r-1][$i-$z][1].','.($r+1);
                } else {
                    $row[$r][$i] = $row[$r-1][$i];
                }
            }
        }
    }
}

print_r($row);
/**
 * 输出最后一个图的矩阵形状，自下而上0-4
 * 每个小格子的数据[9, 0,4,5]，表示总价值为10，物品的组成为第0个（没有），第4[2,3]个，第5[2,6]个（物品从1开始）
 */