Set partition minimum difference problem (01 knapsack)

Set partition minimum difference problem(01背包)

A sequence is divided into two sets,Minimize the difference between the sum of the two set numbers.

Consider a backpack,容量为$\frac{sum}{2}$,转化为判定问题.

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5;
int n,s;
int a[N];
bool dp[N];
int main()
{
    
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),s+=a[i];
    int m = s>>1;
    dp[0] = true;
    for(int i=1;i<=n;i++)
    	for(int j=m;j>=a[i];j--)
    		dp[j]|=dp[j-a[i]];
    int ans = 0;
    for(int i=m;i;i--){
    
    	if(dp[i]){
    
    		ans=s-(i<<1);
    		break;
    	}
    }
    printf("%d\n",ans);
    return 0;
}

If you want to output the scheme,Just open another one$pre$Array records the number used,然后dfs输出路径.