arrays - 分区求和算法

Question

我被要求输入一个整数列表，并将它们分成两个总和相等的部分。例如，1 3 5 7 的列表将被划分为 1+7 和 3+5。这是我到目前为止的代码。我只是在寻找比蛮力更快的方法。

#include <iostream>


using namespace std;

int main()
{
   int input,n,temp,sum = 0;
   int Asum, Bsum;
   cout << "Number of inputs: ";
   cin >> n;
   cout << "Enter " << n << " numbers: ";
   int arr[n];
   int partA[n/2];
   int partB[n/2];

   for(int i = 0; i < n; i++)
   {
       cin >> temp;
       arr[i] = temp;
   }
   for(int i = 0; i < n; i ++)
    sum += arr[i];
   cout << sum;

   if(sum %2 !=0)
   {
       cout << "No partition";
   }
   else
   {
       sum/=2;
   }


   return 0;
}

Answer 1

所以我开始了，我们可以将 dp 状态保持为 dp[idx][sum1] 其中 idx 指的是数组中的当前索引，sum1 是分区 1 的总和，使用这些2个参数我们可以提取第三个参数sum2(sum2 = totalSum - sum1)，这将帮助我们减少状态数，剩下的是一个简单的递归dp解决方案

#include<bits/stdc++.h>

using namespace std;

int n, arr[100], tot, dp[100][100000], mark[100];
int solve(int idx, int sum1){
    if(idx == n){
        int sum2 = tot - sum1;
        //cout << sum1 << " " << sum2 << endl;
        if(sum1 == sum2) return 1;return 0;
    }
    if(dp[idx][sum1] != -1) return dp[idx][sum1];
    int v1 = 0, v2 = 0;
    v1 = solve(idx+1, sum1);
    v2 = solve(idx+1, sum1 + arr[idx]);
    if(v1 + v2 > 0) dp[idx][sum1] = 1;
    else dp[idx][sum1] = 0;
    return dp[idx][sum1];
}

void check(int idx, int sum1){
    if(idx == n) return;
    int v1 = solve(idx+1, sum1);
    int v2 = solve(idx+1, sum1 + arr[idx]);
    if(v1 == 1){
        mark[idx] = 1;
        check(idx+1, sum1);
    }else{
        mark[idx] = 2;
        check(idx+1, sum1 + arr[idx]);
    }
}

int main(){
    cin >> n;
    for(int i = 0;i < n;i++) cin >> arr[i], tot += arr[i];
    memset(dp, -1, sizeof dp);
    int ct = solve(0, 0);
    if(ct == 0){
        cout << "No Partition" << endl;
    }else{
        check(0, 0);
        for(int i = 0;i < n;i++) if(mark[i] == 1) cout << arr[i] << " ";cout << endl;
        for(int i = 0;i < n;i++) if(mark[i] == 2) cout << arr[i] << " ";cout << endl;
    }
}

Ideone 链接:https://ideone.com/6MKLK0

还要记住在定义的dp数组中，index的个数是100，也就是说我们可以求解100个元素，所有元素的总和不能超过100000(也就是第二个参数)，如果您想增加更改状态所需的元素数量，所有元素的总和也是如此。