مقدمه
پیش از این برنامه نویسی پویا را مطرح کرده بودیم، امروز یک سبک از برنامه نویسی پویا به اسم Bitmask را به همراه حل مسئله شماره 10911 از UVA مطرح میکنیم، که به نسبت مسئله ساده ای هست. وقتی که بحث پیاده سازی مجموعه ها در میان باشد Bit Mask ها مطرح میشوند.

خلاصه مسئله
در این مسئله که میتوانید جزیاتش را از اینجا بخوانید تعدادی دانشجو برای انجام یک تمرین میبایست به تیم های دوتایی تقسیم بشوند، ورودی مسئله N با شرط کوچک تر بودن از 9، و همچنین موقعیت 2N دانشجو هست هدف مسئله مینیمم سازی مجموع فاصله دو عضو هر تیم هست. ابتدا ممکن است راه حل های حریصانه در شرایط این مسئله درست به نظر برسند. برای مثال هر دانشجو را با نزدیک ترین دانشجو انتخاب نشده جفت کنیم. اما به راحتی میتوان با مثال های نقض پاسخگویی الگوریتم حریصانه را زیر سوال برد. همچنین تبدیل این گراف به یک گراف دو بخشی اشتباه بوده زیرا محدودیتی برای انتخاب همکار یک دانشجو وجود ندارد.

مجموعه با Bitmask
 نحوه نمایش مجموعه در Bitmask به صورت یک عدد مبنای دو میباشد. اگر 16 دانشجو داشته باشیم تمام حالت ها وجود این 16 دانشجو در مجموعه را میتوانیم با  216 حالت نمایش دهیم. هر رقم از این عدد در مبنای دو نمایانگر وجود یا عدم وجود یک عضو مجموعه میباشد. ساده ترین و سریعترین روش دسترسی به ارقام یک عدد در مبنای دو استفاده از عملگر های بیتی میباشد.

راه حل
میتوان با شکستن این مسئله به زیر مسئله های کوچکتر به راه حل قابل اعتمادی از مرتبه (O(N22N رسید، فرض کنید یک مجموعه از 16 دانشجو داریم به ازای هر دانشجو a و b ، مجموع فاصله a تا b و حل مسئله به ازای مجموعه با حذف دو عضو a و b را بدست می آوریم. با بدست آوردن کمینه این عدد در هر مرحله بدیهی هست که به جواب بهینه کل میرسیم. کد Accept شده این مسئله به زبان C++ را میتوانید در زیر مشاهده نمایید.

بهینه سازی
برای حل این مسئله راه حل بهتری از مرتبه زمانی (O(N 2N نیز میتوان مطرح کرد. سعی کنید به منظور تمرین این راه حل را بیابید.


#include<iostream>
#include<cstring>
#include<vector>
#include<cmath>
#include<iomanip>
using namespace std;
#define Author "DemoVersion"

typedef pair<double,double> pdd;

const int sz=1<<17;
double dp[sz];
bool vis[sz];
vector<pdd> els;
int N;
double dist(int i,int j){
    double dy=els[i].first-els[j].first;
    double dx=els[i].second-els[j].second;
    double ret=dy*dy+dx*dx;
    ret=sqrt(ret);
    return ret;
}
double go(int mask,int cnt){
    double ret,tret;
    int i,j,nm;
    if(vis[mask]){
        return dp[mask];
    }
    if(cnt==2){
        for(i=0;i<N;i++){
            if(mask & (1<<i))break;
        }
        for(j=i+1;j<N;j++){
            if(mask & (1<<j))break;
        }
        ret=dist(i,j);

    }else{
        ret=3000*8;
        for(i=0;i<N;i++){
            if((mask & (1<<i))==0)continue;
            for(j=i+1;j<N;j++){
                if((mask & (1<<j))==0)continue;
                nm=mask;
                nm^=(1<<i);
                nm^=(1<<j);
                tret=go(nm,cnt-2);
                tret+=dist(i,j);
                ret=min(tret,ret);
            }
        }
    }
    vis[mask]=1;
    dp[mask]=ret;
    return ret;
}

int main(){
    ios_base::sync_with_stdio(0);
    int Z=1,nm,i,u,v;
    string skiper;
    while(cin>>N && N){
        N*=2;
        memset(vis,0,sizeof(vis));
        els.clear();
        for(i=0;i<N;i++){
            cin>>skiper>>u>>v;
            els.push_back(pdd(u,v));
        }
        nm=1<<N;
        nm--;
        cout<<"Case "<<Z++<<": "<<setprecision(2)<<fixed<<go(nm,N)<<endl;
    }
    return 0;
}