原题：
房间中有一个天平，房间的宽度为r，有s个砝码，每个砝码的重量是 w i w_i wi。设计一个尽量宽，但是宽度不能超过r的天平，挂住所有砝码。天平全部由长度为1的木棍组成，木棍的每一端要么挂一个挂坠，要么挂另外一个木棍。例如，只有2两个砝码a和b的情况，且重量分别是1/3和2/3，那么木棍应该挂在前2/3处使得天平保持平衡。
砝码的宽度忽略不计，且子天平可以相互重叠。
输入一个整数t，表示有多少个测试用例，然后是r和s，0<r<10, 1<=s<=6，接着是s行，每行表示砝码的重量1<= w i w_i wi<=1000，如果没有解，输出-1，否则输出精度应该保留到10位。
代码：
#include <bits/stdc++.h>using namespace std;
const int maxn = 7;
bool vis[1 << maxn];
double sum[1 << maxn];
int T, n;
double r;
double w[maxn];struct Node {double L, R;Node (): L(0.0), R(0.0) {}
};vector<Node> tree[1 << maxn];void dfs(int subset) {if (vis[subset]) {return;}vis[subset] = true;bool has_child = false;for (int left = (subset - 1) & subset; left; left = (left - 1) & subset) { // 枚举子集has_child = true;int right = subset ^ left; // subset分成left和rightdouble left_d = sum[right] / sum[subset]; // right部分占subset的重量比值就是天平左侧杠杆的长度double right_d = 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++) {Node t;// tree[left][i].L是左子天平左侧杠杆长度// tree[right][i].L是右子天平左侧杠杆长度，考虑overlap的情况// 因为有可能右子天平的左侧杠杆长度特别长t.L = max(left_d + tree[left][i].L, tree[right][j].L - right_d);t.R = max(tree[left][i].R - left_d, right_d + tree[right][j].R);if (t.L + t.R < r) {tree[subset].push_back(t);}}}}if (!has_child) {tree[subset].push_back(Node());}
}int main() {ios::sync_with_stdio(false);cin >> T;while (T--) {cin >> r >> n;for (int i = 0; i < n; i++) {cin >> w[i];}memset(sum, 0, sizeof(sum));memset(vis, false, sizeof(vis));for (int i = 0; i < (1 << n); i++) { // 将所有砝码按照二进制的方式表示tree[i].clear();for (int j = 0; j < n; j++) {if (i & (1 << j)) {sum[i] += w[j]; // sum[i]砝码二进制表示的集合为i的重量和}}}int root = (1 << n) - 1;dfs(root);double ans = -1;for (int i = 0; i < tree[root].size(); i++) {ans = max(ans, tree[root][i].L + tree[root][i].R);}cout << fixed << setprecision(10) << ans << endl;}return 0;
}
思路：
紫书例题，使用位运算标记砝码集合，然后将砝码集合按照二叉树的结构分隔成不同的左右两部分。
保留中间结果的，并记录最大值即可。
