題意：有n道題，每道題在二維平面內的不同位置且給出每道題的坐標，同時給出處理每道題所需的時間p，現在已知裁判的耐心有限，之會花費m個單位時間去做事，做完后回到起始點。
現在的要求是，我要多少個裁判才能對每個問題都處理完，并且同一道題不能有兩個裁判進行處理，并求出總路徑最小的值。
總復雜度O(2^(2*n)+(2^n*n^2))

#include <bits/stdc++.h> #include<cstdio> #include<iostream> #include <iostream> #include <cstring> #define X 10005 #define inf 0x3f3f3f3f #define PI 3.141592653589793238462643383 #define IO ios::sync_with_stdio(false),cin.tie(0), cout.tie(0); #pragma comment(linker, "/STACK:1024000000,1024000000") #define MIN (1<<17) using namespace std; const int maxn = (int)1e5 + 10; typedef long long ll; int greedy(); int TSP_SECOND(); int n,m; int tot;//總的合法物品數 int ans1;//第一問答案 int ans2;//第二問答案 int x[20],y[20];//坐標 int val[20];//權花費的時間 int dp[MIN],state[MIN];//求最少多少個教練 int mp[20][20],isok[MIN];//邊權、合法物品集合 int cost[17][MIN],np[MIN];//多旅行商問題用到 void init() {tot=0;//memset(map,0,sizeof(map));for(int i=0;i<(1<<n);++i) np[i]=inf;///for(int i=0;i<=n;++i)for(int j=0;j<(1<<n);++j)cost[i][j]=inf;cost[0][1]=0;} int Enumeration_subset(int x) {int sum=0;for(int i=0;i<n;++i)//所在的集合iif(x&(1<<i))sum+=val[i];return sum<=m; } //將2^n種地點的選擇集合壓縮成2^n個物品(2^n個狀態,因為每個任務在一個教練的下有被選擇和不被選擇兩種狀態)，物品的權值為集合內的點權之和， //如果總和<=m，那么他是一種合法的組合(說明是一個裁判可以在m的范圍內可以把這些任務完成)，存起來。 //這樣就得到tot種合法組合，對這tot種組合進行01背包(注意是對合法的組合進行01背包)，dp[i]表示容量為i時的最小費用(轉化為對應得前i個二進制位位1得狀態所需要的教練數），和常規的背包不同(但本質是一樣的。) //狀態轉移方程:dp[i] = min(dp[i],dp[j]+1) //(j為i的子集(注意j是i的子集),i = j | state[k]并且j和state[k]沒有交集，state[k]表示第k個合法物品) int DP_FIRST() {//int mmin=inf;for(int i=0;i<(1<<n);++i) dp[i]=inf;dp[0]=0;for(int i=0;i<tot;++i){for(int j=(1<<n)-1;j>=0;--j){if(dp[j]==inf)continue;if((j+state[i])!=(j|state[i]))continue;//兩種狀態不能有交集 也可寫成if((j&state[i])!=0) 在poj2923中可以看到dp[j+state[i]]=min(dp[j+state[i]],dp[j]+1);//}}return dp[(1<<n)-1]; } int main() {while(cin>>n>>m){init();for(int i=0;i<n;++i)cin>>x[i]>>y[i];for(int i=0;i<n;++i)cin>>val[i];for(int i=1;i<(1<<n);++i){isok[i]=Enumeration_subset(i);if(isok[i])state[tot++]=i;}ans1=DP_FIRST(); //狀態壓縮01背包去求最少多少個教練//ans1=greedy(); //greedy求解if(ans1==inf){cout<<-1<<' '<<-1<<endl;continue;}//不能完成所有的任務ans2=TSP_SECOND();cout<<ans1<<' '<<ans2<<endl;}return 0; } /* 貪心得思想去求解最少要用多少個教練的個數，每次一個教練都是從任務花費的時間最大的時候開始進行計算，直到不能解決新的任務結束 之后在對下一個教練進行op， */ int greedy() {int temp[20],vis[20];for(int i=0;i<n;++i)temp[i]=val[i],vis[i]=0;sort(temp,temp);for(int i=1;i<=n;++i){int rest=m;for(int j=n-1;j>=0;--j)if(!vis[j]&&temp[j]<=rest)rest-=temp[j],vis[j]=1;for(int j=n-1;j>=0&&vis[j]==1;--j){if(j==0)return i;}}return inf; } /* 第二問：多旅行商問題即mTsp，感覺挺經典的，思路是將mtsp轉化成普通的tsp，然后再將各個tsp合并成答案。 先要O(2^n*n^2)的預處理得到np[i]表示一個裁判走的集合為i的所有地點又回到最初的點的最少權值和， 然后np[i] = min(np[i],np[k|(1<<0)]+np[(i-k)|(1<<0)])(i必須包含0節點，因為子集可能不含0節點，所以要和1<<0或起來，這樣才是將兩個裁判所走的邊權和合并)。 */ void GetDist() {for(int i=0;i<n;++i){for(int j=i+1;j<n;++j){mp[i][j]=mp[j][i]=ceil(sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])));}} } int TSP_SECOND() {GetDist();for(int i=1;i<(1<<n);++i)//求出各種路徑一種裁判的消費if(isok[i]){for(int j=0;j<n;++j){if(i&(1<<j)){np[i]=min(np[i],cost[j][i]+mp[j][0]);for(int k=0;k<n;++k)if((i&(1<<k))==0)cost[k][i|(1<<k)]=min(cost[k][i|(1<<k)],cost[j][i]+mp[j][k]);}}}for(int i=1;i<(1<<n);++i)//多裁判消費if(i&1)for(int j=(i-1)&i;j;j=(j-1)&i)np[i]=min(np[i],np[j|1]+np[(i-j)|1]);return np[(1<<n)-1]; }

?

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的【hdu4281状态压缩+01背包+多旅行商问题】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。