Ural 1005 Stone pile

//搜索,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的包里装石头,价值与重量相等
//
Accepted
0.031     3933 KB

#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;
}

posted on 2010-06-13 16:32 田兵 阅读(179) 评论(0)  编辑 收藏 引用 所属分类: URAL


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年6月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

导航

统计

常用链接

留言簿(2)

随笔分类(65)

随笔档案(65)

文章档案(2)

ACM

搜索

积分与排名

最新随笔

最新评论

阅读排行榜