怎样自己动手做微官网站,舟山网站设计,wordpress 3.1,海外广告优化师1049. 最后一块石头的重量 II 参考
备注: 当物体容量也等同于价值时, 01背包问题的含义则是利用好最大的背包容量sum/2, 使得结果尽可能的接近或者小于 sum/2 等价: 尽可能的平分成相同的两堆, 其差则为结果, 比如 (abc)-d, (ac)-(bd) , 最终的结果是一堆减去另外一堆的和, 问…1049. 最后一块石头的重量 II 参考
备注: 当物体容量也等同于价值时, 01背包问题的含义则是利用好最大的背包容量sum/2, 使得结果尽可能的接近或者小于 sum/2 等价: 尽可能的平分成相同的两堆, 其差则为结果, 比如 (abc)-d, (ac)-(bd) , 最终的结果是一堆减去另外一堆的和, 问题则转换成01背包 class Solution {
public:int lastStoneWeightII(vectorint stones) {int sum 0;for (int i 0; i stones.size(); i) {sum stones[i];}vectorint dp(sum / 2 1, 0);for (int i 0; i stones.size(); i) {for (int j sum / 2; j 0; j--) {if (j - stones[i] 0) {dp[j] max(dp[j], dp[j - stones[i]] stones[i]);}}}return (sum - dp[sum / 2]) - dp[sum / 2];}
};494. 目标和 回溯法会超时
转换成01背包问题:
A B sumA - B targetA (target sum) / 2B (sum - target) / 2 其中A相当于weigh, nums[i]相当于价值 当 A (target sum) / 2 向下取整时, 说明不存在结果 当 abs(target) sum 时不存在
五部曲:
dp[j]: 填满j包括j这么大容积的包有dp[j]种方法 (假设A为容量)初始化: dp[0] 1
class Solution {
public:int findTargetSumWays(vectorint nums, int target) {int sum 0;for (int i 0; i nums.size(); i) {sum nums[i];}int A (target sum) / 2;if ((target sum) % 2) return 0;if (abs(target) sum) return 0;vectorintdp(A 1, 0);dp[0] 1;for (int i 0; i nums.size(); i) {for (int j A; j nums[i]; j--) {dp[j] dp[j - nums[i]];}}return dp[A];}
};474.一和零
