Question

简单01背包问题

Alphard要给bpt和AngelClover分糖果。糖果共有n个，每个糖果的甜味值为si(1 <= i <= n)。Alphard希望分给bpt的糖果甜味值和与分给AngelClover的糖果甜味值和的差最小，且糖果不能有剩余。Alphard想要知道这个最小的差值，于是他请你帮忙。
Input
第一行有一个正整数T，表示输入数据的组数。接下来有T组输入数据，每组数据第一行是一个正整数n( 1 <= n <= 50 )表示糖果的个数，接下来一行有n个整数si(1 <= i <= n)，表示第i个糖果的甜味值( |si| <= 50 )。
Output
对于每组输入数据，输出一个非负整数，表示最小差值。每个整数占一行，不要有多余的空格和空行。
Sample Input
2
4
1 2 3 4
5
1 2 3 4 5
Sample Output
0
1
为什么我的程序错了...
program Project1;
var s:array[-101..101]of longint;
f:array[-6001..6001]of longint;
k,q,n,m,i,j:longint;
function max(x,y:longint):longint;
begin
if x>y then exit(x);
exit(y);
end;
begin
readln(k);
for q:=1 to k do
begin
fillchar(f,sizeof(f),0);
fillchar(s,sizeof(s),0);
readln(n);
for i:=1 to n do
read(s[i]);
m:=0;
for i:=1 to n do
begin
m:=m+s[i];
s[i]:=s[i]*2;
end;
for i:=1 to n do
for j:=m downto s[i] do
f[j]:=max(f[j],f[j-s[i]]+s[i]);
writeln(m-f[m]);
end;
end.

Answer 1

你的思路有点问题，不应该找他的最大值，应该要看看距离最大值的一半最近的地方在哪？
给你一个程序参考：
program t;
var s:array[-101..101]of longint;
f:array[-6001..6001]of boolean;
k,q,n,m,i,j:longint;
function max(x,y:longint):longint;
begin
if x>y then exit(x);
exit(y);
end;
begin
readln(k);
for q:=1 to k do
begin
fillchar(f,sizeof(f),false);f[0]:=true;
fillchar(s,sizeof(s),0);
readln(n);
for i:=1 to n do
read(s[i]);
m:=0;
for i:=1 to n do
begin
m:=m+s[i];
s[i]:=s[i]*2;
end;
for i:=1 to n do
for j:=m downto s[i] do
if not f[j] then
begin
if f[j-s[i]] then f[j]:=true;
end;
i:=m;
while not(f[i]) do dec(i);
writeln(m-i);
end;
end.

追问

我是把 两倍的甜味度 做 物品，总甜味度 做 背包容量 ，求最小差值的..
两倍是为了避免 总甜味度 除 2 出现余数 导致结果不准。。
是在找距离最大值的一半最近的方案.
能不能别发代码，看看我写的错在哪里，帮我改改？我加分....

追答

你的策略有错误！！！

追问

请解释下。。。
还有，为什么我自己测的数据全都是对的？（用你给的程序测了。。。）
求详细解释。。。

追答

这就是道简单动规题，要找距离总甜味度的和的一半最近是多少，
设甜味度的和为sum，其中一部分糖果甜味度为s1且与sum/2的差最小，
则最小差值即结果为 |s2-s1| （s2为另一部分糖果的甜味度，也可表示为sum-s1）
以上是分析，以下为动归方程：
f[i,j]:=f[i,j-s[i]] or f[i,j]; f为布尔型数组；
f[i,j]表示前i个糖果能否得到的甜味度j，若f[i,j]=true则能，若f[i,j]=false则不能。

我写的程序做了一个空间优化，把数组降至一维数组，
如果不懂，可以看看DD牛的《背包九讲》。

Answer 2

不会