学习动态规划

的背包。

第i件物品的重量是weight[i]得到的价值是value[i]

。

每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。

可以得到递推公式对于第i件物品对于重量为j的背包产生的最大价值为不放入该件物品时的最大价值dp[i-1][j]与放入该物品时的最大价值dp[i-1][j-weight[i]]values[i]的最大值即

dp[i][j]

如果我们把dp[i-1]的数据先copy到第i行那么得到递推公式

dp[i][j]

那完全可以我们只维护一行数组每次遍历物品时用上一层的dp[j]来进行更新即可更新为一维数组递归公式为

dp[j]

注意如果用一维数组表示那么只能倒序才能保证每个物品只放入了一次具体可以自己推导。

416.

先求出目标和以及初始化dp[target]还是很直观。

但是对于初次接触背包问题来讲在想dp[j]表示的涵义时没想明白。

dp[j]应该表示为当背包最大容量为j时放入i和不放入i所能产生的最大价值是多少。

如果最大容量为target且当前所能产生的最大价值为target时表示存在。

转化为本题为加入在不超过当前最大和的情况下放入哪些元素能使的当前的目标和最大接近target

class

Math.max(dp[j],dp[j-nums[i]]nums[i]);if(dp[j]

target)