网上销售,保姆seo教程,页面设计属于什么专业,微信商城如何开通文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析#xff1a;本题需要得到石头之间两两粉碎之后的最小值#xff0c;那么一个简单的思路就是将这堆石头划分成大小相… 文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析本题需要得到石头之间两两粉碎之后的最小值那么一个简单的思路就是将这堆石头划分成大小相近的两小堆石头然后粉碎这样得到的结果必然是最优值。那么如何划分呢我们可以将所有石头的质量求和假设和为 s u m sum sum以 s u m / 2 sum/2 sum/2为界限。一堆石头质量设为 w 1 w_1 w1有 w 1 ≤ s u m / 2 w_1 \leq sum/2 w1≤sum/2而另外一堆石头质量 w 2 w_2 w2有 w 2 ≥ s u m / 2 w_2 \geq sum/2 w2≥sum/2且 w 1 w 2 s u m w_1 w_2sum w1w2sum。因为要求两堆石头粉碎之后的质量 Δ \Delta Δ最小所以划分出来的两堆石头重量越接近越好等同于 w 1 w_1 w1和 w 2 w_2 w2越接近于 s u m / 2 sum/2 sum/2。所以我们可以将 m i n ( Δ w 2 − w 1 ) min(\Delta w_2- w_1) min(Δw2−w1)问题转化为 m a x ( w 1 ) , s . t . w 1 ≤ s u m / 2 max(w_1), s.t. w_1 \leq sum/2 max(w1),s.t.w1≤sum/2即在这个数组中找到和最接近sum/2的子集。这是一个01背包问题。最终的最小质量 Δ m i n w 2 − w 1 s u m − 2 ∗ w 1 \Delta_{min} w_2- w_1 sum - 2*w_1 Δminw2−w1sum−2∗w1。 程序如下
class Solution {
public:int lastStoneWeightII(vectorint stones) {int sum accumulate(stones.begin(), stones.end(), 0);vectorint dp(vectorint(sum/2 1, 0));for (int i 0; i stones.size(); i) { // 遍历物品for (int j sum/2; j stones[i]; j--) { // 遍历背包容量dp[j] max(dp[j], dp[j - stones[i]] stones[i]);}}return sum -2 * dp[sum/2];}
};复杂度分析
时间复杂度 O ( n 2 ) O(n^2) O(n2)。空间复杂度 O ( n ) O(n) O(n)。
三、完整代码
# include iostream
# include vector
# include numeric
# include algorithm
using namespace std;class Solution {
public:int lastStoneWeightII(vectorint stones) {int sum accumulate(stones.begin(), stones.end(), 0);vectorint dp(vectorint(sum/2 1, 0));for (int i 0; i stones.size(); i) { // 遍历物品for (int j sum/2; j stones[i]; j--) { // 遍历背包容量dp[j] max(dp[j], dp[j - stones[i]] stones[i]);}}return sum -2 * dp[sum/2];}
};int main() {Solution s1;vectorint stones { 2,7,4,1,8,1 };int result s1.lastStoneWeightII(stones);cout result endl;system(pause);return 0;
}end
