1. 问题

有N件物品和一个容量为V的背包。放入第i件物品耗费的空间是C，得到的价值是W。求解装入背包的物品的价值总和最大是多少。（每种物品仅有一件，可选择放与不放）

2. 分析

这是一维动态规划问题，也叫背包问题。
公式：

# f(i, v)表示前i件物品中选择若干放入一个容量为v的背包可获得的最大价值。
f(i, v) = max(f(i-1), v), f(i-1, v-c[i] + w[i])

时间复杂度： O(V * N)
空间复杂度： O(V * N)

降维：

dp[v] = max(dp[v], dp[v-c[i]] = w[i])

时间复杂度： O(V * N)
空间复杂度： O(V)

3. 解决

代码：

<?php
$thing = [
    ['c' => 9, 'w' => 10],
    ['c' => 4, 'w' => 5],
    ['c' => 6, 'w' => 4],
    ['c' => 7, 'w' => 9],
];
$package = [];
$cacheThing = [];
function package($space) {
    // echo $space."\t";
    global $thing, $package, $cacheThing;
    if (isset($package[$space])) return $package[$space];
    $maxMoney = 0;
    foreach ($thing as $item) {
        if (($reSpace = $space - $item['c']) <= 0) continue;
        if (($w = package($reSpace) + $item['w']) <= $maxMoney) continue;
        $package[$space] = $maxMoney = $w;
        // print_r($package);
        $cacheThing[$space] = $item['w'];
    }
    return $maxMoney;
}
echo package(20);
print_r($package);
print_r($cacheThing);