#include#include #include #include #include using namespace std; void search(const vector &sugers, int weight, int start, int count, int &res,int target,int& minchazhi,int sum,int n) { //用搜索法 //我自己在糖果堆中选糖果，对于每一颗糖果，我可以选或者不选 //如果选，count+1，表示我当前手里的糖果的数量 //每次选完，我手里的糖果达到总数量的一半后，就进行手里糖果重量与总质量一半的最小差值minchazhi的更新 //并记录在当前最小差值下的我手里糖果的质量,最后的res就是结果 if (count == n/2) { if (abs(2 * weight - sum) < minchazhi) { //这次搜索的结果比上次更好，用res记录这个更好的结果 res = weight; minchazhi = abs(2 * weight - sum); } } else { if (start < sugers.size()) { //还可以继续搜索 search(sugers,weight, start + 1, count, res, target, minchazhi, sum,n); search(sugers, weight+sugers[start], start + 1, count+1, res, target, minchazhi, sum,n); } } } int main() { int n; while (cin >> n) { vector sugers(n); int sum = 0; for (int i = 0; i < n; i++) { cin >> sugers[i]; sum += sugers[i]; } int target = sum / 2; int res = 0, minchazhi = INT_MAX; search(sugers, 0, 0, 0,res,target,minchazhi,sum,n); if(res>sum-res) cout < << ' ' << res << endl; else cout < << ' ' << sum-res << endl; } return 0; }
一、
#include#include #include using namespace std;int Min = 1e10;int num;int sum = 0;int res;void dfs(vector & stone, int w, int start, int cnt) { if (cnt == num) { if (abs(w * 2 - sum) < Min) { res = w; Min = abs(w * 2 - sum); } } else { if (start == stone.size()) return; dfs(stone, w, start + 1, cnt); dfs(stone, w + stone[start], start + 1, cnt + 1); }}int main(){ int n; cin >> n; vector stone(n); for (int i = 0; i < n; i++) { cin >> stone[i]; sum += stone[i]; } num = n / 2; sort(stone.begin(), stone.end()); dfs(stone, 0, 0, 0); if (res * 2 > sum) cout << sum - res << " " << res << endl; else cout << res << " " << sum - res << endl; return 0;}