快捷搜索:

LanQiao-ALGO-1004 无聊的逗 (动态规划: 0-1背包问题) -- (LeetCode 416. 分割等和子集 变种题)

一、题目:

输入样例:

4
1 2 3 1

输出样例:

3

数据规模:

n<=15

二、解题思路:

首先通过题意我们可以知道题目要求的是从一堆棍子中分别无重复的取 m , n根棍子。m根棍子拼接在一起长度为 Len_m,n根棍子拼接在一起长度为 Len_n。 问当 Len_m == Len_n 时, Len_m 或者 Len_n 最长能多长?

    好了我们先理解到这里,现在来看这道题的阉割版 解题思路:
提醒:不了解 0-1 背包问题思想的请自行百度学习

这道题需要有一种转换的思维:

  1. nums如果要想有两个子序列相等,那么sum一定是偶数,奇数肯定不能分成两个相等序列。
  2. sum/2 可以看作背包最大容量,nums[i] 可以看作物品质量和价值(相等),那么这道题就可以转换为每件物品只能用一次,哪些物品装入背包里物品价值总和最大,由于物品质量和价值相等,所以其实尽量装满背包,价值总和就是最大。(0-1 背包问题)
  3. 判断最大价值是否等于 sum/2, 成立则返回 true, 反之返回 false。
  4. 套用 0-1 背包问题状态转移方程模板算法求解。
    实现代码:
class Solution {
          
   
public:
    bool canPartition(vector<int>& nums) {
          
   
        int n = nums.size();
        // 数组长度为 1 直接返回 false
        if (n < 2) return false;
        int sum = accumulate(nums.begin(), nums.end(), 0);
        int maxNum = *max_element(nums.begin(), nums.end());
        // 判断是否为奇数,奇数直接返回false
        if (sum & 1) return false;
        // 背包最大容量
        int target = sum / 2; 
        // 如果物品中最大质量大于背包最大容量,肯定无法分成两个相等子序列,返回 false
        if (maxNum > target) return false;
        // 建立背包
        vector<vector<int> > dp(n, vector<int>(target + 1, 0));
        // 初始化背包
        for (int i = 0; i < n; i++) dp[i][0] = 0;
        for (int j = nums[0]; j <= target; j++) dp[0][j] = nums[0];
        // 前 i 个物品放置进容量为 j 的背包中的最优解,一直递推
        for (int i = 1; i < n; i++) {
          
   
            for (int j = 1; j <= target; j++) {
          
   
                if (j < nums[i]) {
          
   
                    dp[i][j] = dp[i - 1][j];
                } else {
          
   
                    dp[i][j] = max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i]);
                }
            }
        }
        return dp[n - 1][target] == sum/2;
    }
};
以上算法可以进行空间优化,但优化后代码不好理解,使用标准0-1背包算法更容易理解。

好了,咱们回到正题,《ALGO-1004 无聊的逗》 这道题就好理解多了。这道题变化其实就在不一定所有棍子都会被使用,可能有些棍子不会被使用。但你需要求出 Len_m == Len_n 时,Len_m 或者 Len_n 最长能多长,那么就始终离不开 sum (棍子长度总和) 为偶数, 这样才有可能 Len_m == Len_n。 那我想先给所有棍子排个序,然后从第一个根棍子开始删起, 具体删除哪根棍子,条件是能使 sum - nums[i] 为偶数, 把 sum 为偶数的 nums 拿去判断是否能分割成两个相等子序列,存在则返回sum/2,否则返回 0。 每次操作与上一次操作结果取最大值,最终 ans 结果即为答案。


三、实现代码:

#include <bits/stdc++.h>
using namespace std;

// 判断是否能分割成两个相等子序列,存在则返回sum/2,否则返回 0
int getPartitionValue(vector<int> nums) {
          
   
    int n = nums.size();
    if (n < 2) return 0;
    int sum = accumulate(nums.begin(), nums.end(), 0);
    int maxNum = *max_element(nums.begin(), nums.end());
    int target = sum / 2;
    if (maxNum > target) return 0;
    // 建立背包
    vector<vector<int> > dp(n, vector<int>(target + 1, 0));
    // 初始化背包
    for (int i = 0; i < n; i++) dp[i][0] = 0;
    for (int j = nums[0]; j <= sum/2; j++) dp[0][j] = nums[0];
    for (int i = 1; i < n; i++) {
          
   
        for (int j = 1; j <= target; j++) {
          
   
            if (j < nums[i]) {
          
   
                dp[i][j] = dp[i - 1][j];
            } else {
          
   
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i]);
            }
        }
    }
    return dp[n - 1][target] == sum/2 ? sum/2 : 0;
}

int main() {
          
   
    int n;
    cin>>n;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) cin>>nums[i];

    sort(nums.begin(), nums.end()); // 排序
    int sum = accumulate(nums.begin(), nums.end(), 0); // 累加

    int i = 0;
    int ans = 0;
    // 不删除棍子情况下,sum如果为偶数,判断是否能分割成两个相等子序列,并保存结果
    if (sum % 2 == 0) ans = getPartitionValue(nums);
    // 如果每次总和是偶数,都去判断是否存在可分成使得两个子集的元素和相等,如果存在返回值,否则返回 0, 每次取最大值
    while (i < nums.size()) {
          
   
        sum = accumulate(nums.begin(),nums.end(), 0);
        if ((sum - nums[i]) % 2 == 0) {
          
   
            nums.erase(nums.begin()+i); // 删除这个元素
            ans = max(getPartitionValue(nums), ans); // 每次取最大值
            i = 0; // i 置为 0
            continue;
        }
        i++;
    }
    cout<<ans<<endl;
    return 0;
}
看来思路还不错 😆 😆 ,耗时和内存占用都很低。(以上算法还可以优化,比如: 0-1背包的空间优化,这里就不作优化了)

这里贴一个之前百度找的唯一解法:(Java 编写)

看上去像是暴力解法,实在没看懂怎么做的,博主也不回消息😣 😣 ,后来自己灵感一来,直接 AC 了,哈哈,坚持就是胜利!

这位博主做法的耗时和内存占用如下:
经验分享 程序员 职场和发展