//搜索，O(2^n)
#include<iostream>
//#include<limit.h>
#include<cmath>
using namespace std;
int w[21]={0};
int n,total=0,ans=INT_MAX;
void search(int i,int now)
{
if(i>n)
{
if(ans>abs(total-2*now))ans=abs(total-2*now);
return ;
}
search(i+1,now+w[i]);
search(i+1,now);
}
int main()
{
cin>>n;
for(int i=1;i<=n; i++)
{ cin>>w[i];total+=w[i];}
search(1,0);
cout<<ans<<endl;
return 0;
}
DP：01背包 往容量為total/2的包里裝石頭，價值與重量相等
//
#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;
}