poj1015 01二维背包

/*
给定辩控双方给每个人的打分p[i],d[i],
dp[j][k]表示前i个人有j个被选定,选定的人的辩控双方打分差之和是k,此状态下的最大辩控双方和
按01背包做,体积一维是1,体积二维是辩控双方打分差,价值是辩控双方打分和
要求体积一维不得超过m,体积二维在体积一维=m的情况下最小
状态转移方程:dp[j][k]=max(dp[j][k],dp[j-1][k-(a[i]-b[i])]+a[i]+b[i])
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
struct node{
int a,b,sum,dif;
}p[];
int dp[][]; int main(){
int n,m,tt=;
while(scanf("%d%d",&n,&m),n){
memset(dp,-,sizeof dp); vector<int> path[][];
for(int i=;i<=n;i++){
scanf("%d%d",&p[i].a,&p[i].b);
p[i].sum=p[i].a+p[i].b;
p[i].dif=p[i].a-p[i].b;
} int max_diff=m*;//由于两者之差可能是负数,所以在所有差值上增加一个max_diff dp[][max_diff]=;
for(int i=;i<=n;i++)
for(int j=m;j>=;j--)//逆序枚举,保证每个候选人最多被选一次
for(int k=;k<=max_diff*;k++)
if(dp[j-][k]>=)
if(dp[j-][k]+p[i].sum>dp[j][k+p[i].dif]){
dp[j][k+p[i].dif]=dp[j-][k]+p[i].sum;
path[j][k+p[i].dif]=path[j-][k];
path[j][k+p[i].dif].push_back(i);
} int i,min_diff;
for(i=;i<=max_diff;i++)
if(dp[m][max_diff-i]>=||dp[m][max_diff+i]>=) break;
//找到最小的差 i
if(dp[m][max_diff-i]>dp[m][max_diff+i]) min_diff=max_diff-i;
else min_diff=max_diff+i;
cout << (dp[m][min_diff]+i)/ << " " <<(dp[m][min_diff]-i)/ << endl;
for(int i=;i<m;i++)
cout << path[m][min_diff][i] << " ";
puts(" ");
}
}
上一篇:android 数据库添加字符串 添加失败 解决方案


下一篇:锋利的jQuery(第二版)源码下载地址