刚看完题目想Greedy，试着举反例，没找到。但是看数据规模像是搜索，还是特简单的那种DFS，发现效率还挺高！提交，AC。
后来看到有DP的做法。原问题等价于从n个物品中选取若干个，其重量不超过sum/2，且重量达到最大。只要令权值等于重量即可。
以下是我的代码，DFS程序：
#include<iostream>
#include<stdlib.h>
#define maxn 27
#define INF 20000007
using namespace std;
long n,sum,ans,w[maxn];
void dfs(long dep,long now)
{
if(dep>n)
{
if(ans>abs(now-(sum-now))) ans=abs(now-(sum-now));
return;
}
dfs(dep+1,now);
dfs(dep+1,now+w[dep]);
}
int main()
{
cin>>n;
sum=0;
for(long i=1;i<=n;i++)
{
cin>>w[i];
sum+=w[i];
}
// Input
ans=INF;
dfs(1,0);
cout<<ans<<endl;
return 0;
}
posted on 2010-09-05 22:27
lee1r 阅读(1540)
评论(1) 编辑 收藏 引用 所属分类:
题目分类：搜索