算法无聊的逗：逗志芃在干了很多事情后终于闲下来了，然后就陷入

2023-01-11 11:28 527次浏览 0 条评论 C++

问题描述

　　逗志芃在干了很多事情后终于闲下来了，然后就陷入了深深的无聊中。不过他想到了一个游戏来使他更无聊。他拿出n个木棍，然后选出其中一些粘成一根长的，然后再选一些粘成另一个长的，他想知道在两根一样长的情况下长度最长是多少。

输入格式

　　第一行一个数n，表示n个棍子。第二行n个数，每个数表示一根棍子的长度。

输出格式

　　一个数，最大的长度。

样例输入

4
1 2 3 1

样例输出

参考代码：

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

// 如果两个子集的元素和相等时，返回nums总和除以 2，否则返回 0
int getPartitionValue(vector<int> nums) {
    int n = nums.size();
    if (n < 2) {
        return false;
    }
    int sum = accumulate(nums.begin(), nums.end(), 0);
    int maxNum = *max_element(nums.begin(), nums.end());
    if (sum & 1) return 0;
    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;
    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;
}

赞助网站

<< · Back Index ·>>

小码农

算法无聊的逗：逗志芃在干了很多事情后终于闲下来了，然后就陷入

发表评论

取消回复

小码农

算法无聊的逗：逗志芃在干了很多事情后终于闲下来了，然后就陷入

相关文章

发表评论

取消回复