phmezymoon 2014-08-12 22:27:05
点我顶贴
收藏
删除
/*将所有人的体重的一半看成背包的容量,每个人的体重既是花费又是价值,如果s为奇数,则背包的容量会少算0.5,最终结果会少1,所以s为奇数时要加1*/
# include <iostream>
# define max(a,b) a>b?a:b
using namespace std ;
int main (void)
{
int n ;
int m ;
int dp[1000] = {0} ;
int w[100] ;
int i , j ;
int s = 0 ;
int t ;
cin>>n;
for (i = 1 ; i <= n ; i++)
{
cin>>w[i] ;
s += w[i] ;
}
m = s / 2 ;
for (i = 1 ; i <= n ; i++)
for (j = m ; j >= w[i] ; j--)
dp[j] = max(dp[j] ,dp[j - w[i]] + w[i]) ;
t = (m - dp[m]) * 2 ;
if (s % 2 == 1)
cout<<t+1<<endl ;
else
cout<<t<<endl ;
return 0 ;
}