XidianOJ 1036 分配宝藏

题目描述

两个寻宝者找到一个宝藏，里面包含着n件物品，每件物品的价值是w[i]。suma代表寻宝者A所获物品的总价值，sumb代表寻宝者B所获物品的总价值，请问怎么分配，能使得|suma - sumb|（即suma与sumb之差的绝对值）最小。

输入

有多组输入数据，第一行为一个数字T，代表有T组输入数

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
int w[201],f[50000];
int main(){
    int time,T,i,j;
    scanf("%d",&T);
    for (time=1;time<=T;time++){
        scanf("%d",&n);
        int sum = 0;
        for (i=1;i<=n;i++){
            scanf("%d",&w[i]);
            sum += w[i];
        }
        int weight = sum / 2;
        memset(f,0,sizeof(f));
        for (i=1;i<=n;i++){
            for (j=weight;j>=w[i];j--){
                f[j] = max(f[j],f[j-w[i]]+w[i]);
            }
        }        
        int res = sum-2*f[weight];
        if (res < 0) res = -res;
        printf("%d
",sum-(2*f[weight]));
        
    }
    return 0;
} 

据 (0<T<=50)。
接下来为T组数据，每组数据分为两行：
第一行有一个整数n, 表示物品个数，其中0<n<=200.
第二行有n个整数，第i个正数w[i]代表第i件物品的价值，其中0<w[i]<=200.
注意：所有数据均为正整数。

输出

一共T行。
对于每组数据，输出一个整数，表示|suma-sumb|。

--正文

背包问题，以总和的1/2来作为总容量