本文主要是介绍poj1015(dp输出路径)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：点击打开链接
题意：有n个人，每个人有一个D值和P值，求选出m个人，使得|∑(D)-∑(P)|最小，如果最小值相同，则选择|∑(D)+∑(P)|较大的，输出选出的人和∑(D)，∑(P)
代码：
#include <vector>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
vector<int> path[8005][25];
int a[205],b[205];
int dp[8005][25],sum[8005][25];
int main(){int n,m,i,j,k,p,cas,tmp;int ansa,ansb,tmpa,tmpb;cas=1;while(scanf("%d%d",&n,&m)!=EOF&&(n||m)){memset(dp,0,sizeof(dp));memset(sum,0,sizeof(sum));for(i=0;i<=40*n;i++)for(j=0;j<=m;j++)path[i][j].clear();for(i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);dp[0][0]=1; //dp[i][j]表示能否用j个数，使得差值和为ifor(i=1;i<=n;i++){ //sum[i][j]表示j个数，差值是i时和的最大值tmp=a[i]-b[i]+20; //因为是求绝对值最小，因此需要将所有数加上for(j=40*m;j>=tmp;j--){ //20避免出现负数for(k=m;k>=1;k--){if(!dp[j-tmp][k-1])continue;if(!dp[j][k]){ //看dp[j][k]是否被询问过sum[j][k]=sum[j-tmp][k-1]+a[i]+b[i];path[j][k]=path[j-tmp][k-1];path[j][k].push_back(i);dp[j][k]=1;}else if(sum[j][k]<sum[j-tmp][k-1]+a[i]+b[i]){sum[j][k]=sum[j-tmp][k-1]+a[i]+b[i];path[j][k]=path[j-tmp][k-1];path[j][k].push_back(i);} //path记录路径}}}p=0; //正常要找0上下最小的，现在因为每个数while(!dp[20*m-p][m]&&!dp[20*m+p][m]) //都加上20,所以找20*m上下的p++;if(!dp[20*m+p][m]){ansa=abs(-p+sum[20*m-p][m])/2; //已知a+b和a-b求a和bansb=(sum[20*m-p][m]+p)/2; //要注意正负号tmpa=20*m-p;}else if(!dp[20*m-p][m]){ansa=abs(p+sum[20*m+p][m])/2;ansb=(sum[20*m+p][m]-p)/2;tmpa=20*m+p;}else{if(sum[20*m+p][m]>sum[20*m-p][m]){ansa=abs(p+sum[20*m+p][m])/2;ansb=(sum[20*m+p][m]-p)/2;tmpa=20*m+p;}else{ansa=abs(-p+sum[20*m-p][m])/2;ansb=(sum[20*m-p][m]+p)/2;tmpa=20*m-p;}}printf("Jury #%d\n",cas++);printf("Best jury has value %d for prosecution and value %d for defence:\n",ansa,ansb);for(i=0;i<path[tmpa][m].size();i++)printf(" %d",path[tmpa][m][i]);printf("\n\n");}return 0;
}
这篇关于poj1015(dp输出路径)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
