UVALive - 3403 Mobile Computing

题意：给出房间的宽度r和s个挂钩的重量。设计一个尽量宽，但宽度不超过房间宽度的天平，挂着所有的挂钩。挂钩的宽度不计，且不相同的挂钩可以互相重叠

思路：每次将当前集合分成两个不相交的子集合，每次都构造出子集的最大的天平，最后从子集中选出最大的

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN = 65;

double r,w[10],value[MAXN],ans;
struct node{
    double l1,l2;
}nw;
vector<node> adj[MAXN];
int vis[MAXN],num[MAXN],n;

void dfs(int state){
    double l1,l2;
    bool flag = false;
    if (vis[state])
        return;
    vis[state] = true;
    for (int i = (state&(state-1)); i > 0; i = ((i-1)&state)){
        int j = state ^ i;
        dfs(i);
        dfs(j);
        for (int s = 0; s < num[i]; s++)
            for (int p = 0; p < num[j]; p++){
                l1 = value[j] / (value[i]+value[j]);
                l2 = value[i] / (value[i]+value[j]);
                nw.l1 = max(adj[i][s].l1+l1,adj[j][p].l1-l2);
                nw.l2 = max(adj[i][s].l2-l1,adj[j][p].l2+l2);
                if (nw.l1 + nw.l2 <= r){
                    adj[state].push_back(nw);
                    num[state]++;
                }
            }
        flag = true;
    }
    if (!flag){
        nw.l1 = nw.l2 = 0;
        adj[state].push_back(nw);
        num[state]++;
    }
}

int main(){
    int t;
    scanf("%d",&t);
    while (t--){
        scanf("%lf%d",&r,&n);
        for (int i = 0; i < n; i++)
            scanf("%lf",&w[i]);
        for (int i = 0; i < (1<<n); i++){
            adj[i].clear();
            value[i] = 0;
            for (int j = 0; j < n; j++)
                if (i & (1<<j))
                    value[i] += w[j];
        }
        memset(num,0,sizeof(num));
        memset(vis,0,sizeof(vis));
        dfs((1<<n)-1);
        ans = -1;
        for (int i = 0; i < num[(1<<n)-1]; i++){
            if (adj[(1<<n)-1][i].l1 + adj[(1<<n)-1][i].l2 > ans)
                ans = adj[(1<<n)-1][i].l1 + adj[(1<<n)-1][i].l2;
        }
        printf("%.20f\n",ans);
    }
    return 0;
}

UVALive - 3403 Mobile Computing

原文：http://blog.csdn.net/u011345136/article/details/18505599