定义dp[i][j]表示取前i个物品，在背包容量不超过j的情况下能得到的最大价值。
对于第i个物品，可以选择 或者不选择。
- 如果不选择第i个物品放入背包，那么dp[i][j]其实就是等于dp[i-1][j]，即只考虑前i-1个商品，不超过容量j所能得到的最大值。
- 如果要选择放入第i个物品到背包，那么此时只要再考虑前i-1个商品，容量不超过j-weight[i-1]的时候能得到的最大值,即dp[i-1][j-weight[i-1]]. 因为第i个物品的容量是weight[i-1]。此时的最大值再加上物品i的价值即可。
- 这里需要考虑j-weight[i-1]可能小于0，即当前物品i的容量已经大于背包容量了，此时的最大值是其上一个状态
- 最后要求的就是
//n个物品，包容量w，每个物品的大小weight和价值value, 求不超过w 最大价值
function knapsack($w, $n, $weight, $value) {
$dp = array_fill(0, $n + 1, array_fill(0, $w + 1, 0));
for ($i = 1; $i < $n; $i++) {
for ($j = 1; $j <= $w; $j++) {
if ($j >= $weight[$i-1]) {
//不放入第i个物品，放入第i个物品，取最大值
$dp[$i][$j] = max($dp[$i - 1][$j], $dp[$i - 1][$j - $weight[$i - 1]] + $value[$i-1]);
} else {
$dp[$i][$j] = $dp[$i-1][$j];
}
}
}
return $dp[$n][$w];
}
https://leetcode-cn.com/problems/partition-equal-subset-sum/
leetcode 416 分隔等和子集。
function canPartition($nums) {
$sum = array_sum($nums);
if ($sum % 2 == 1) {
return false;
}
$sum = $sum / 2;
$len_n = count($nums);
$dp = array_fill(0, $len_n + 1, array_fill(0, $sum + 1, false));
for ($i = 0; $i <= $len_n; $i++) {
$dp[$i][0] = true;
}
//dp[i][j]表示 对于前i个物品，容量为j的情况下，要是能恰好装满包，则为true，否则为false
for ($i = 1; $i <= $len_n; $i++) {
for ($j = 1; $j <= $sum; $j++) {
if ($j - $nums[$i-1] >= 0) {
//不选择第i个数字，表示只从前i-1个数里选，凑够容量j的情况，那么就跟上一个状态一样。 ||
//选择第i个数字的话， 只有看前i-1个数里能不能再选出j-weight[i-1]的情况就行。
$dp[$i][$j] = $dp[$i - 1][$j] || $dp[$i-1][$j - $nums[$i-1]];
} else {
$dp[$i][$j] = $dp[$i-1][$j];
}
}
}
return $dp[$len_n][$sum];
}
经过空间压缩后的。注意的是此时的j要从sum开始往小遍历，也就是从后往前填表。因为
$dp[$i][$j] = $dp[$i - 1][$j] || $dp[$i-1][$j - $nums[$i-1]];
上面这个状态转移方程表示当前i,j状态下的值与i-1状态有关。是上一行(次)的数据。
$dp[$j] = $dp[$j] || $dp[$j - $nums[$i-1]];
要还是从前往后遍历的话，上次的数据可能会被覆盖掉。
比如现在j=8，当前数字是4 那么dp[8]会和上次的dp[8]和上次的dp[4]有关，你要是从前开始遍历，上次存储的dp[4]的值就被这次的覆盖了，从而出错。而从后往前遍历则不会出现这种情况。当时我也是理解了好久没看明白。后来填了表，才看懂。下面的文章讲的也不错。
tech.souyunku.com/Christal-R/…
function canPartition($nums) {
$sum = array_sum($nums);
if ($sum % 2 == 1) {
return false;
}
$sum = $sum / 2;
$len_n = count($nums);
$dp = array_fill(0, $sum + 1, false);
$dp[0] = true;
for ($i = 1; $i <= $len_n; $i++) {
for ($j = $sum; $j >= 1; $j--) {
if ($j - $nums[$i-1] >= 0) {
$dp[$j] = $dp[$j] || $dp[$j - $nums[$i-1]];
}
}
}
return $dp[$sum];
}
labuladong.gitbook.io/algo/dong-t…