来自"NOCOW"

---

Solution From w4ppsxy: 这个题目我们可以采用0/1背包的方法。背包的容量为sumv div 2然后找小于sum div 2且最大的容量作为分割的一个值即可

---

Program From Accoropitor:
 
DP
 
var
  n,i,j,m,max:longint;
  a,f:array[1..100000]of longint;
begin
  read(n);
  for i:=1 to n do
    begin
      read(a[i]);
      inc(m,a[i]);
    end;
  max:=m div 2;
  for i:=1 to n do
    for j:=max downto a[i] do
      if f[j]<f[j-a[i]]+a[i] then
        f[j]:=f[j-a[i]]+a[i];
  write(m-f[max]-f[max]);
end.

---

search:

#include<iostream>
using namespace std;
 
const int N=21;
int w[N];
int n,total,ans;
 
void search(int i,int now)
{
     if (i>n)
     {  
        if (abs(total-2*now)<ans) ans=abs(total-2*now);
        return;
     }
     search(i+1,now+w[i]);
     search(i+1,now);
}
int main()
{   
    std::cin>>n;
    for(int i=1;i<=n;i++)
    {
       cin>>w[i];
       total+=w[i];
    }
    ans=3144046;
    search(1,0);
    cout<<ans<<endl;
    return 0;
}
 
---->from 3144046cjc

3144046cjc

program ural1005; const

 maxn=20;

var

 w:array[1..maxn]of longint;
 n,i:byte;
 total,min,s:longint;

procedure search(l:byte);

 begin
   if l=n then begin
     if abs(total-s*2)<min then min:=abs(total-s*2)
   end
   else begin
     search(l+1);
     inc(s,w[l]);
     search(l+1);
     dec(s,w[l]);
   end;
 end;

begin

 read(n);
 total:=0;
 for i:=1 to n do begin
   read(w[i]);
   inc(total,w[i]);
 end;

 min:=total;s:=0;
 search(1);

 writeln(min);

end.

这个就是死搜吧……只是算差值的可以优化。

var a,b:array[1..20] of longint;
    n,i,j,s,k,l,m:longint;
begin
  readln(n);s:=0;
  for i:=1 to n do
    begin
      read(a[i]);
      dec(s,a[i]);
    end;
  fillchar(b,sizeof(b),0);
  k:=0;l:=1 shl n-1;m:=maxlongint;
  while k<l do
    begin
      i:=n;
      while b[i]=1 do
        begin
          b[i]:=0;dec(s,a[i]);dec(s,a[i]);
          dec(i);
        end;
      b[i]:=1;inc(s,a[i]);inc(s,a[i]);
      if abs(s)<m then m:=abs(s);
      inc(k);
    end;
  writeln(m);
end.

----
DP：01背包 往容量为total/2的包里装石头，价值与重量相等
// Accepted 
加个DP程序吧
 0.031     3933 KB 
//http://www.cppblog.com/tianlearn-language/archive/2010/06/13/117799.html
----
#include<iostream>
using namespace std;
const int SIZE=21;
int w[SIZE]={0};
int dp[SIZE*100000/2+5]={0};
int main()
{
    int n,i,total,v,j;
    cin>>n;
    for(i=1,total=0; i<=n ; i++ )
        { cin>>w[i]; total+=w[i]; }
 
    v=total/2;
 
    for(i=1; i<=n; i++)
    for(j=v; j>=w[i]; j-- )
      if(dp[j]<dp[j-w[i]]+w[i])
        dp[j]=dp[j-w[i]]+w[i];
 
    cout<<total-2*dp[v]<<endl;
    return 0;
}