问题
有 n 件物品和一个最多能背重量为 w 的背包。第 i 件物品的重量是 weight[i],得到的价值是 value[i] 。
每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。
重量 | 价值 | |
---|---|---|
物品0 | 1 | 15 |
物品1 | 3 | 20 |
物品2 | 4 | 30 |
416. 分割等和子集
判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
优先计算总和,如果是奇数不可能平均分配,返回 false。然后计算出 背包问题中的容量 sum = sum / 2。至于重量和价值就是 nums 中存储的,即重量和价值一致。
1 |
|
推演过程:nums = [1,5,11,5]
初始化,在没有物品或者没有空间的情况下,全部初始化为0
物品/空间 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
没有物品 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
物品 A | 0 | |||||||||||
物品 B | 0 | |||||||||||
物品 C | 0 | |||||||||||
物品 D | 0 |
空间不足的情况下,就不能放入新的物品,那就继承前面装入物品价值的结果。
见下面:空间为 1 的情况下,无法放入物品 B,那就继承前面的结果 1,因为放不下物品 B,但能够放下物品 A。
物品/空间 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
没有物品 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
物品 A | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
物品 B | 0 | 1 | ||||||||||
物品 C | 0 | |||||||||||
物品 D | 0 |
空间足够的情况下,有两种选择,一种是选择放下当前物品,另一种是选择不放下当前物品。
为什么会存在这两种选择的情况呢?因为有得必有失,当你选择放下当前物品,那么你的空间会有损失。
见下面:现在你要放入 物品 B,空间大小为 5,明显是可以容下。那究竟选择放还是不放呢?
放:dp[i - 1][j - nums[i - 1]] + nums[i - 1]
不放:dp[i - 1][j]
放入物品的话,首先要取得减去容纳当前物品剩余空间对应的dp,再加上当前物品价值(因为我们已经选择容纳该物品)。
如果没有放入物品,情况就和空间不足类似,继承前面的价值结果。
物品/空间 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
没有物品 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
物品 A | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
物品 B | 0 | 1 | 1 | 1 | 1 | 5 | ||||||
物品 C | 0 | |||||||||||
物品 D | 0 |
1049 最后一块石头的重量 II
为了让这些石头尽可能粉碎,就让选择的那些石头尽可能接近总和的平均值,和上面那道题类似。
1 |
|
返回值特别要注意,由于我们已经计算出能容下的最大价值(重量)A ,因此要用总和 减去 两倍的 A。
两倍的原因是用来相互抵消的缘故。
494. 目标和
这道题有数学关系在里面,我们知道数组里面的元素可以是正数,也可以是负数。
那我们就把 全部的正数视为 a,全部的负数视为 b,得到如下确定的关系式:
1 |
|
由于 target 和 sum 都会是确定的值,那么 a 和 b 就是确定的。
由于题目说 nums 是正数集合,那么问题就变成 在 nums 中找到一个子集,使得其元素和等于 a。
从 nums 数组中找到组合,这些组合的和为 a。
1 |
|
在后面得题目中,在求装满背包有几种方法的情况下,递推公式一般为:dp[i][j] += dp[i - 1][j - nums[i-1]]
dp[0][0] = 1
是因为 0(行) 可以组成 0(列)。