5 5 8 13 27 14
3
本题的用暴力搜索,想好解答树,一边搜索一边剪枝
#include <iostream> #include <algorithm> #include <vector> #include <cmath> #include <numeric> using namespace std; int ans = 0; int sumWeight = 0; void dfs(int index,int v, vector<int>& weight){ if (index == weight.size()) return ; ans = min(ans,abs(sumWeight-2*v)); dfs(index+1,v,weight); dfs(index+1,v+weight[index],weight); } int main(){ int n; while(cin >> n){ vector<int> weight(n); for(int i = 0; i < n ; ++ i) cin >> weight[i]; sumWeight = accumulate(weight.begin(),weight.end(),0); ans = sumWeight; dfs(0,0,weight); cout<<ans<<endl; } }
原文:http://www.cnblogs.com/xiongqiangcs/p/3702883.html