#PHPで動的計画法を用いてナップザック問題を解く

##動的計画法とは
対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法
（メモ化再帰はまた別途）

##ナップザック問題とは
容量 C のナップサックが一つと、n 種類の品物（各々、価値とサイズ）が与えられたとき、ナップサックの容量 C を超えない範囲でいくつかの品物をナップサックに詰め、ナップサックに入れた品物の価値の和を最大化するにはどの品物を選べばよいか？という問題

##コード

Knapsack.php

/*
ナップザック
 */

class Knapsack {
    public $knapsack;      //ナップザック
    public $knapsackCount; //ナップザックの容量
    public $products;      //商品。商品はサイズと価値がある

    public function __construct($capacity) {
        $this->knapsack      = array_fill(0, $capacity + 1, 0);
        $this->knapsackCount = $capacity;
        $this->product       = array();
    }

    public function addProduct($size, $value) {
        $this->products[] = array('size' => $size, 'value' => $value);
    }

    public function solveKnapsack() {
        //ナップザックに詰め込んだ時の値を初期化
        $napValue = array_fill(0, $this->knapsackCount + 1, 0);

        //ナップザックの容量を表示する
        echo '<table  border="1" frame="box">';
        echo '<tr>';
        echo '<th>ナップサックの大きさ</th>';
        for ($i = 1; $i < $this->knapsackCount + 1; $i++) {
            echo '<td>' . $i . '</td>';
        }
        echo '</tr>';

        //扱う商品を1つずつ増やしていく
        $productCount = count($this->products);
        for ($i = 0; $i < $productCount; $i++) {
            //$napIndexの初期値は商品のサイズから。
            for ($napIndex = $this->products[$i]['size']; $napIndex < $this->knapsackCount + 1; $napIndex++) {
                $newValue = $napValue[$napIndex - $this->products[$i]['size']] + $this->products[$i]['value'];
                if ($newValue > $napValue[$napIndex]) {
                    $napValue[$napIndex] = $newValue;
                }
            }
            //表示
            echo '<tr><th>' . ($i + 1) . '番目の商品まで使用</th>';
            for ($napIndex = 1; $napIndex < $this->knapsackCount + 1; $napIndex++) {
                echo '<td>' . $napValue[$napIndex]. '</td>';
            }
            echo '</tr>';
        }
        echo '</table>';
    }
}

knapsackTest.php

<!DOCTYPE html>
<html lang="ja">
<head>
<meta charset="UTF-8">
</head>
<body>
<?php
require_once './part/Knapsack.php';

//ナップザックの容量を設定
$knapsack = new Knapsack(32);

//ナップザックの商品を追加
$knapsack->addProduct(2,2);
$knapsack->addProduct(3,4);
$knapsack->addProduct(5,7);
$knapsack->addProduct(6,10);
$knapsack->addProduct(9,30);

//ナップザックを解く
$knapsack->solveKnapsack();
?>
</body>
</html>

##参考書籍
プログラミングの宝箱アルゴリズムとデータ構造第2版

##参考サイト
https://www.sist.ac.jp/~suganuma/kougi/other_lecture/SE/opt/dynamic/dynamic.htm