題意：給出房間寬度 r 和 s 個(gè)掛墜的重量 wi，設(shè)計(jì)一個(gè)盡量寬的天平，掛著所有掛墜。天平由一些長度為 1 的木棍組成，木棍的每一端要么掛一個(gè)掛墜，要么掛另外一個(gè)木棍。

這題卡了很久，看了很多大神的代碼，終于把細(xì)節(jié)都搞懂了。

將掛墜所有可能的集合的重量算出來，再用二進(jìn)制的方式枚舉子集（左子樹）和補(bǔ)集（右子樹）構(gòu)成二叉樹，算出左右的寬度。

代碼：

#include <iostream> #include <cstring> #include <vector> using namespace std;const int MAX = 6;struct Tree{double L, R; //樹的左邊和右邊的長度Tree():L(0), R(0){} };double width, w[MAX], sum[1<<MAX]; int vis[1<<MAX]; vector<Tree> tree[1<<MAX]; //枚舉出來的結(jié)點(diǎn)可以組合成多個(gè)樹void dfs(int subset); //枚舉二叉樹int main(){freopen("input.txt", "r", stdin);int T;cin >> T;while(T--){int s;scanf("%lf%d", &width, &s);for(int i=0; i<s; i++){scanf("%lf", &w[i]);}//初始化 memset(sum, 0, sizeof(sum));for(int i=1; i<(1<<s); i++){tree[i].clear(); //清空樹int k = 1;for(int j=0; j<s; j++){ //算出當(dāng)前集合所有結(jié)點(diǎn)的重量和if(k & i){sum[i] += w[j];}k = (k << 1);} }//進(jìn)行枚舉int root = (1<<s) - 1;memset(vis, 0, sizeof(vis));dfs(root);//得到最大的答案double ans = -1;for(int i=0; i<tree[root].size(); i++){ans = max(tree[root][i].L + tree[root][i].R, ans);} printf("%.10lf\n", ans);}} void dfs(int subset){if(vis[subset])return;vis[subset] = 1;bool hasChild = false;for(int left = ((subset-1) & subset); left > 0; left = ((left-1) & subset)){ //枚舉集合 hasChild = true;int right = subset ^ left; //left 的補(bǔ)集double l = sum[right] / sum[subset]; //左臂長度double r = sum[left] / sum[subset]; //右臂長度 dfs(left); dfs(right); //把左右樹的子樹也枚舉出來for(int i=0; i<tree[left].size(); i++){ //將枚舉出的左右子樹組合起來 for(int j=0; j<tree[right].size(); j++){Tree t;t.L = max(tree[left][i].L + l, tree[right][j].L - r);t.R = max(tree[right][j].R + r, tree[left][i].R - l);if(t.L + t.R < width){ //如果滿足條件，枚舉結(jié)果加一 tree[subset].push_back(t); }}}}if(!hasChild){ //葉子結(jié)點(diǎn)的左右臂為零 tree[subset].push_back(Tree());}}

?

轉(zhuǎn)載于:https://www.cnblogs.com/lighter-blog/p/7216349.html

總結(jié)

以上是生活随笔為你收集整理的UVa 1354 天平难题 枚举二叉树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。