51Nod 1007 正整數分組 0-1背包

求n個數能組合成最接近總和的一半

然後0-1背包。判斷最接近一半值的數

#include<iostream>  
#include<queue>  
#include<vector>  
#include<stack>  
#include<algorithm>
#include<cmath> 
using namespace std;  
int main(){
	int n;
	cin>>n;
	int a[101];
	int sum=0;
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
		sum+=a[i];
	}
	int fz=sum;
	sum=sum/2;
	int f[10010]={0};
	for(int i=0;i<n;i++){
		for(int j=sum;j>=a[i];j--){
			f[j]=max(f[j],f[j-a[i]]+a[i]);
		}
	}
	cout<<abs(fz-2*f[sum]);
	return 0;
}