当前位置：网站首页>Set partition minimum difference problem (01 knapsack)

Set partition minimum difference problem (01 knapsack)

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

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,容量为 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;
}

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

原网站

版权声明
本文为[Harris-H]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/216/202208041409223696.html

边栏推荐

猜你喜欢

随机推荐