分區求和算法

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的總和，使用這兩個參數，我們可以提取第三paramater那被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陣列定義，否索引是100，這意味着我們可以解決它100個元素，並且所有這些元素的總和不應該超過100000（這是第二個參數），如果您想增加需要更改狀態的元素數量，所有元素的總和也一樣。