1.6.8天平难题
【摘要】
Description
给出房间的宽度r和s个挂坠的重量wi，设计一个尽量宽(但宽度不超过房间宽度r)的天平，挂着所有的挂坠。天平由一些长度为1的木棍组成。木棍的每一端要么挂着一个挂坠，要么挂着另一个木棍。如图所示，设n和m分别是两端挂的总重量，要让天平平衡，必须满足na=mb（力矩相等）
例如，如果有3...
Description
给出房间的宽度r和s个挂坠的重量wi，设计一个尽量宽(但宽度不超过房间宽度r)的天平，挂着所有的挂坠。天平由一些长度为1的木棍组成。木棍的每一端要么挂着一个挂坠，要么挂着另一个木棍。如图所示，设n和m分别是两端挂的总重量，要让天平平衡，必须满足na=mb（力矩相等）
例如，如果有3个重量分别为1，1，2的挂坠，有3种平衡的天平，如图所示。
挂坠的宽度忽略不计，且不同的子天平可以互相重叠，如图所示，宽度为(1/3)+1+(1/4)。
Input
输入第一行为数据组数。每组数据前两行为房间宽度r和挂坠的数量s(0<r<10,1<=s<=6)。以下s行每行为一个挂坠的重量Wi(1<=Wi<=1000)。输入保证不存在天平的宽度恰好在r−10^5和r+10^5之间（这样可以保证不会出现精度问题）。
Output
对于每组数据，输出最优天平的宽度。如果无解，输出−1。
你的输出和标准答案的绝对误差不应该超过1e−8
Sample Input 1
5 1.3 3 1 2 1 1.4 3 1 2 1 2.0 3 1 2 1 1.59 4 2 1 1 3 1.7143 4 1 2 3 5
Sample Output 1
-1 1.3333333333333335 1.6666666666666667 1.5833333333333335 1.7142857142857142
一个天平可看做一棵二叉树，对于一个确定的二叉树，可以算出每一个挂坠的位置，那么这个天平的宽度也可以计算出来，那么问题就转化成了枚举所有的二叉树。
在这里给出三种方法。
方法一：
自底上向上构造，每次任选择2个挂坠合并为一个。
-
#include<iostream>
-
#include<cstring>
-
#include<algorithm>
-
#include<iomanip>
-
#define f(i,l,r) for(i=(l);i<=(r);i++)
-
using namespace std;
-
const int MAXN=8;
-
double W,w[MAXN],ans,l[MAXN],r[MAXN];
-
int n,vis[MAXN];
-
inline void dfs(int cur)
-
{
-
int i,j;
-
if(cur==n){
-
f(i,1,n){
-
if(vis[i]) continue;
-
if(l[i]+r[i]>W) continue;
-
ans=max(ans,l[i]+r[i]);
-
}
-
return;
-
}
-
f(i,1,n){
-
if(vis[i]) continue;
-
f(j,1,n){
-
if(i==j||vis[j]) continue;
-
vis[i]=1;
-
double a=w[j]/(w[i]+w[j]),b=1-a;
-
w[j]+=w[i];
-
double tmpl=l[j],tmpr=r[j];
-
l[j]=max(l[i]+a,-b+l[j]);
-
r[j]=max(r[j]+b,-a+r[i]);
-
dfs(cur+1);
-
vis[i]=0;
-
w[j]-=w[i];
-
l[j]=tmpl;
-
r[j]=tmpr;
-
}
-
}
-
}
-
int main()
-
{
-
ios::sync_with_stdio(false);
-
int i,j,T;
-
cin>>T;
-
while(T--){
-
memset(vis,0,sizeof(vis));
-
memset(l,0,sizeof(l));
-
memset(r,0,sizeof(r));
-
ans=-1;
-
cin>>W>>n;
-
f(i,1,n){
-
cin>>w[i];
-
}
-
dfs(1);
-
cout<<fixed<<setprecision(10)<<ans<<endl;
-
}
-
return 0;
-
}
方法二：自顶向下回溯构造，用一个一维数组保存二叉树，i的父亲就是i+i。
-
#include<iostream>
-
#include<cstring>
-
#include<algorithm>
-
#include<iomanip>
-
#define f(i,l,r) for(i=(l);i<=(r);i++)
-
#define ff(i,r,l) for(i=(r);i>=(l);i--)
-
using namespace std;
-
const int MAXN=8;
-
double w[MAXN],W,l[1<<MAXN],r[1<<MAXN],val[1<<MAXN],ans;
-
int n,tree[1<<MAXN],vis[MAXN];
-
inline void judge(int cur)
-
{
-
int i;
-
memset(l,0,sizeof(l));
-
memset(r,0,sizeof(r));
-
memset(val,0,sizeof(val));
-
ff(i,cur,1){
-
if(~tree[i]){
-
val[i]=w[tree[i]];
-
}
-
else{
-
int lson=i<<1,rson=lson|1;
-
val[i]=val[lson]+val[rson];
-
double a=val[rson]/val[i],b=1-a;
-
l[i]=max(l[lson]+a,-b+l[rson]);
-
r[i]=max(r[rson]+b,-a+r[lson]);
-
if(l[i]+r[i]>W) return;
-
}
-
}
-
ans=max(ans,l[1]+r[1]);
-
}
-
inline void dfs(int cur,int pos,int res)
-
{
-
int i;
-
if(res==0){
-
judge(cur-1);
-
return;
-
}
-
if(~tree[cur>>1]){
-
dfs(cur+1,pos,res);
-
return;
-
}
-
if(pos<res){
-
tree[cur]=-1;
-
dfs(cur+1,pos+1,res);
-
tree[cur]=0;
-
}
-
if(pos==1&&res>pos) return;
-
f(i,1,n){
-
if(vis[i]) continue;
-
vis[i]=1;
-
tree[cur]=i;
-
dfs(cur+1,pos-1,res-1);
-
vis[i]=0;
-
}
-
}
-
int main()
-
{
-
ios::sync_with_stdio(false);
-
int i,j,T;
-
cin>>T;
-
while(T--){
-
memset(vis,0,sizeof(vis));
-
memset(tree,0,sizeof(tree));
-
ans=-1;
-
cin>>W>>n;
-
f(i,1,n){
-
cin>>w[i];
-
}
-
if(n==1){ //necessary special judge
-
cout<<0<<endl;
-
continue;
-
}
-
tree[1]=-1;
-
dfs(2,2,n);
-
cout<<fixed<<setprecision(10)<<ans<<endl;
-
}
-
return 0;
-
}
方法三：自顶向下枚举子集构造，每次枚举左子树用到哪些子集，那么右子树就是剩下的子集，递归构造即可，另外根据对称性，一个子集若已经构造过，那么剪枝。
-
#include<iostream>
-
#include<cstring>
-
#include<vector>
-
#include<algorithm>
-
#include<iomanip>
-
#define f(i,l,r) for(i=(l);i<=(r);i++)
-
using namespace std;
-
const int MAXN=10;
-
struct Tree{
-
double l,r;
-
};
-
vector<Tree> tree[MAXN<<3];
-
double w[MAXN],W,sum[MAXN<<3],ans;
-
int n,vis[MAXN<<3];
-
inline void dfs(int S)
-
{
-
int i,j,l,r,flag=1;
-
if(vis[S]) return;
-
vis[S]=1;
-
for(l=(S-1)&S;l;l=(l-1)&S){
-
flag=0;
-
r=S^l;
-
double d1=sum[r]/sum[S];
-
double d2=sum[l]/sum[S];
-
dfs(l);
-
dfs(r);
-
for(i=0;i<tree[l].size();i++){
-
for(j=0;j<tree[r].size();j++){
-
Tree tmp;
-
tmp.l=max(d1+tree[l][i].l,-d2+tree[r][j].l);
-
tmp.r=max(d2+tree[r][j].r,-d1+tree[l][i].r);
-
if(tmp.l+tmp.r<W) tree[S].push_back(tmp);
-
}
-
}
-
}
-
if(flag) tree[S].push_back((Tree){0,0});
-
}
-
int main()
-
{
-
ios::sync_with_stdio(false);
-
int T,i,j,root;
-
cin>>T;
-
while(T--){
-
cin>>W>>n;
-
memset(sum,0,sizeof(sum));
-
memset(vis,0,sizeof(vis));
-
f(i,1,n){
-
cin>>w[i];
-
}
-
f(i,1,(1<<n)-1){
-
tree[i].clear();
-
f(j,0,n-1){
-
if(i&(1<<j)){
-
sum[i]+=w[j+1];
-
}
-
}
-
}
-
root=(1<<n)-1;
-
dfs(root);
-
ans=-1;
-
for(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;
-
}
之后会有补充，敬请期待！
文章来源: blog.csdn.net，作者：irrationality，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/weixin_54227557/article/details/120616271
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）