本文主要是介绍POJ 2184 Cow Exhibition （处理负值的01背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【题目链接】：click here~~
【题意】：
题意：给定n头牛的聪明指数S和幸福指数F，如果存在S的和TS>=0与F的和TF>=0同时成立时，
输出TS与TF的和的最大值sum，否则，输出0。
【思路】：
转化问题，求s和为某个固定值时候最大的f和值，然后遍历这些所有的s和以及对应的f和值，求出总和总和最大的那个。
那么这样就是一个0-1背包问题，可以把s值理解为费用，f值理解为价值
dp[c]代表s和为c时候，f和能取到的最大值。
状态转移方程： dp[c]=max{dp[c], dp[c-s[i]+f[i]}
注意：因为s有小于0的情况，s的范围在[-1000,1000]之间，最多有100头牛，所以和的范围在[-100000,100000]之间，为了避免负数作为下标，s和都加上100000，整体的范围就变为[0,200000]。
当s[i]>0的时候，dp[c]的计算顺序从大往小计算，因为在计算第i头牛的最优f和时，dp[c-s[i]]是前i-1头牛的最优f和，而这个值在dp[c]的左侧，所以我们从右往左计算，这样就可以利用前i-1的最优解，不会覆盖。同理当s[i]<0的时候，dp[c]的计算顺序从小往大计算，因为dp[c-s[i]]这个时候dp[c]的右侧了。
代码：
/*
* Problem: POJ No.2184
* Running time: 236MS
* Complier: G++
* Author: herongwei
* Create Time: 20:45 2015/9/10 星期三
* 巧妙的01背包
*
*/
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#define CLR(c,v) (memset(c,v,sizeof(c)))
using namespace std;template <typename _T>
inline _T Max(_T a,_T b){return (a>b)?(a):(b);
}template <typename _T>
inline _T Maxx(_T a,_T b,_T c){return (a>Max(b,c))?(a):(Max(b,c));
}
const int N = 1e2+ 10;
const int M = 1e5;
const int INF = 0x3f3f3f3f;int dp[2*M+10];
int zs[N],ym[N];
int Ncase;int main()
{while(~scanf("%d",&Ncase)){CLR(zs,0);CLR(ym,0);CLR(dp,-INF);dp[M]=0;for(int i=0; i<Ncase; ++i) scanf("%d %d",&zs[i],&ym[i]);for(int i=0; i<Ncase; ++i){if(zs[i]>0)//>0 then in reversed order{for(int j=2*M; j>=zs[i]; --j)//this order ensure that we put every item just for one timedp[j]=Max(dp[j],dp[j-zs[i]]+ym[i]);}else{ //if negative number,have a look at the prooffor(int j=0; j<2*M+zs[i]; ++j)dp[j]=Max(dp[j],dp[j-zs[i]]+ym[i]);}}int ans=0;for(int i=M; i<=2*M; ++i){if(dp[i]>=0&&dp[i]+i-M>ans)ans=dp[i]+i-M;}printf("%d\n",ans);}return 0;
}
/*
sample input
5
-5 7
8 -6
6 -3
2 1
-8 -5
sample ouput
8
*/
这篇关于POJ 2184 Cow Exhibition （处理负值的01背包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
