剛看完題目想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 閱讀(1585)
評論(1) 編輯 收藏 引用 所屬分類:
題目分類：搜索