当前位置：网站首页>集合划分差最小问题(01背包)

集合划分差最小问题(01背包)

2022-08-04 14:09:00 【Harris-H】

集合划分差最小问题(01背包)

一个序列分为两个集合，使得两个集合数的和差值最小。

考虑背包，容量为 s u m 2 \dfrac{sum}{2} 2sum​，转化为判定问题。

#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;
}

如果要输出方案，就再开一个 p r e pre pre数组记录使用的数，然后dfs输出路径。

原网站

版权声明
本文为[Harris-H]所创，转载请带上原文链接，感谢
https://harris.blog.csdn.net/article/details/126157233

边栏推荐

猜你喜欢

随机推荐