深圳网站建设价格,wordpress文章打赏,昆山 网站设计,成立咨询公司需要什么条件最后一块石头的重量 II
力扣原题 有一堆石头#xff0c;用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合#xff0c;从中选出任意两块石头#xff0c;然后将它们一起粉碎。假设石头的重量分别为 x 和 y#xff0c;且 x y。那么粉碎的可能结…最后一块石头的重量 II
力扣原题 有一堆石头用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合从中选出任意两块石头然后将它们一起粉碎。假设石头的重量分别为 x 和 y且 x y。那么粉碎的可能结果如下
如果 x y那么两块石头都会被完全粉碎如果 x ! y那么重量为 x 的石头将会完全粉碎而重量为 y 的石头新重量为 y-x。
最后最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下就返回 0。
示例 1 输入stones [2,7,4,1,8,1] 输出1 解释 组合 2 和 4得到 2所以数组转化为 [2,7,1,8,1] 组合 7 和 8得到 1所以数组转化为 [2,1,1,1] 组合 2 和 1得到 1所以数组转化为 [1,1,1] 组合 1 和 1得到 0所以数组转化为 [1]这就是最优值。 示例 2 输入stones [31,26,33,21,40] 输出5 提示
1 stones.length 30
1 stones[i] 100思路分析 解决背包最多装多少这道题体现在尽可能接近一半
给定一堆石头的重量每次可以选择两块石头将它们粉碎。如果两块石头的重量相同则两块石头都会被粉碎如果两块石头的重量不同则较重的石头会变为重量差而较轻的石头会被粉碎。最终只会剩下一块石头要求返回此石头的最小可能重量。如果没有石头剩下则返回 0。 思考最后是返回最小可能那是不是可以考虑成把石头尽可能相等的分成两堆然后两堆各之和相减不就是最后的最小重量了嘛。
这个问题可以转化为 01 背包问题。我们可以将每块石头的重量视为物品的重量而要求的最小可能重量则是背包能装下的最大重量。需要注意的是因为石头最终只剩下一块所以我们要尽可能地使得剩余石头的重量接近总重量的一半这样最后的结果就会最小。
状态定义
定义一个一维的动态规划数组 dp其中 dp[j] 表示背包容量为 j 时所能达到的最大石头重量。
状态转移方程
我们需要考虑当前石头是否放入背包中的两种情况
如果不放入当前石头 stones[i - 1]则 dp[j] 保持不变即 dp[j] dp[j]如果放入当前石头 stones[i - 1]则 dp[j] dp[j - stones[i - 1]] stones[i - 1]表示背包容量为 j - stones[i - 1] 时的最大重量加上当前石头的重量。
综合以上两种情况状态转移方程为
dp[j] Math.max(dp[j], dp[j - stones[i - 1]] stones[i - 1])初始化
我们需要对动态规划数组进行初始化当没有石头或背包容量为0时。
解题步骤
首先计算出所有石头的总重量 sum。初始化背包容量为总重量的一半即 target sum / 2。使用动态规划来求解背包问题。定义一个一维数组 dp其中 dp[j] 表示当背包容量为 j 时能够装下的最大重量。对于每块石头遍历背包容量从 target 到石头重量之间的所有可能取值更新 dp[j] 为 Math.max(dp[j], dp[j - stones[i]] stones[i])。最终返回剩余石头重量和背包能装下的重量之差的绝对值即 Math.abs(sum - 2 * dp[target])。
Java 实现
class Solution {public int lastStoneWeightII(int[] stones) {int sum 0;for (int stone : stones) {sum stone;}int target sum / 2;int[] dp new int[target 1];for (int i 0; i stones.length; i) {//遍历物品for (int j target; j stones[i]; j--) {//遍历背包 注意倒序dp[j] Math.max(dp[j], dp[j - stones[i]] stones[i]);//背包价值最大化的递推公式}}return Math.abs(sum - 2 * dp[target]);}
}通过以上步骤我们可以解决这个石头重量最小化的问题使得剩余石头的重量尽可能接近总重量的一半。
