1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 #include <vector> 5 #include <cstdio> 6 using namespace std; 7 int dp[25][1000]; 8 //int path[25][1000]; 9 vector<int> path[21][801]; 10 int sub[1000]; 11 int add[1000]; 12 int n,m,fix; 13 int main () 14 { 15 int num=0; 16 while (cin>>n>>m&&n&&m) { 17 memset (dp,-1,sizeof(dp)); 18 for (int i=0;i<=m;i++) 19 for (int j=0;j<801;j++) 20 path[i][j].clear(); 21 for (int i=1;i<=n;i++) { 22 int d,p; cin>>d>>p; 23 sub[i]=d-p; 24 add[i]=d+p; 25 } 26 fix=20*m; dp[0][fix]=0; 27 for (int i=1;i<=n;i++) { 28 for (int x=m-1;x>=0;x--) 29 for (int y=0;y<=2*fix;y++) {//因为sub[i]既可以为正也可以为负，所以状态的转移更新的方向 从x=m-1逆推 30 if (dp[x][y]>=0&&dp[x+1][y+sub[i]]<dp[x][y]+add[i]) { 31 dp[x+1][y+sub[i]]=dp[x][y]+add[i]; 32 //path[x+1][y+sub[i]] = i; //这样定义是不行的 因为取m个 当前最优路径是动态的 中间结果可能被再次更新 33 path[x+1][y+sub[i]] = path[x][y]; 34 path[x+1][y+sub[i]].push_back(i); 35 } 36 } 37 } 38 int ans; int a[25]; 39 for (int i=0;i<=fix;i++) if (dp[m][fix-i]>=0||dp[m][fix+i]>=0) {ans=i;break;} 40 ans=dp[m][fix+ans]>dp[m][fix-ans]?ans:-ans;//判断ans的正负 41 int sum1=(dp[m][fix+ans]+ans)/2; 42 int sum2=(dp[m][fix+ans]-ans)/2; 43 int v=fix+ans; 44 /* for (int i=m;i>=1;i--) { 45 a[i]=path[i][v]; 46 //cout<<v<<endl; 47 v-=sub[a[i]]; 48 }*/ 49 printf( "Jury #%d ", ++num ); 50 printf( "Best jury has value %d for prosecution and value %d for defence: ", sum1,sum2); 51 // for (int i=1;i<=m;i++) 52 //cout<<" "<<a[i]; 53 for( int i=0; i < m; i++ ) 54 printf( " %d", path[m][fix+ans][i]); 55 cout<<" "; 56 } 57 return 0; 58 }
poj-1015(状态转移的方向（01背包）和结果的输出）
抓住青春的尾巴。。。