学步园

UVA_562

    这个题目可以将coins的面值和体积等效，然后转化成0-1背包问题。

    背包的体积为总面值的一半，然后求放置物品的最大价值即可，越接近总面值的一半，两个人得到的coins的面值差就会越小。

#include<stdio.h>
#include<string.h>
int a[110], f[50010], N, M, m;
void init()
{
int i;
    M = 0;
    scanf("%d", &N);
for(i = 0; i < N; i ++)
    {
        scanf("%d", &a[i]);
        M += a[i];
    }
    m = M / 2;
}
void solve()
{
int i, j;
    memset(f, 0, sizeof(f));
for(i = 0; i < N; i ++)
for(j = m; j >= a[i]; j --)
if(f[j - a[i]] + a[i] > f[j])
                f[j] = f[j - a[i]] + a[i];
    printf("%d\n", M - 2 * f[m]);
}
int main()
{
int t;
    scanf("%d", &t);
while(t --)
    {
        init();
        solve();
    }
return 0;
}