正題

題目鏈接:http://poj.org/problem?id=1015

---

題目大意

每個人有A值和B值，要求選M個人，使這M個人的|SumA?SumB||SumA?SumB|最小。

---

解題思路

我們用SumA?SumBSumA?SumB作為原本的價格，然后用fi,jfi,j表示已經選了i個人，SumA?SumBSumA?SumB為j時的情況，然后用dd數組統計每個狀態是從哪個轉移過來的，然后進行dp。

注意：c++沒有負數下標，所以要加一個m×20m×20

---

code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m,f[31][801],a[811],b[811],d[31][801],x,wr[31],t; bool write(int x,int y,int z)//判斷路徑是否正確 {while(x&&d[x][y]!=z){y-=a[d[x][y]]-b[d[x][y]];x--;}return !x; } int main() {n=1;while(scanf("%d%d",&n,&m)&&n!=0&&m!=0){memset(f,-1,sizeof(f));memset(d,0,sizeof(d));f[0][m*20]=0;for(int i=1;i<=n;i++){scanf("%d%d",&a[i],&b[i]);}for(int i=1;i<=m;i++)for(int j=0;j<=m*40;j++)if(f[i-1][j]>=0)//有這個狀態for(int k=1;k<=n;k++){if(f[i][j+a[k]-b[k]]<f[i-1][j]+a[k]+b[k]&&write(i-1,j,k))//是否可以轉移{f[i][j+a[k]-b[k]]=f[i-1][j]+a[k]+b[k];d[i][j+a[k]-b[k]]=k;}}printf("Jury #%d\n",++t);int k1=0;while(k1<=m*20&&f[m][m*20+k1]<0&&f[m][m*20-k1]<0) k1++;//尋找答案int ans=f[m][m*20+k1]>f[m][m*20-k1]?m*20+k1:m*20-k1;//計算正負printf("Best jury has value %d for prosecution and value %d for defence:\n",(ans+f[m][ans]-m*20)>>1,(f[m][ans]-ans+m*20)>>1);//輸出for (int i=1,j=m,k=ans;i<=m;i++){wr[i]=d[j][k];k-=a[d[j][k]]-b[d[j][k]];j--;}//記錄方案sort(wr+1,wr+1+m);//按順序for (int i=1;i<=m;i++) printf(" %d",wr[i]);printf("\n\n");} }

總結

以上是生活随笔為你收集整理的POJ1015-Jury Compromise【01背包,dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

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