讨论 / 01背包转化一下
phmezymoon 2014-08-13 13: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 ;

}

查看更多回复
提交回复