Cow Exhibition POJ - 2184 （01背包）

题目

 https://cn.vjudge.net/problem/POJ-2184

题意

n头母牛 有两个值 让你选若干个 使他们两个值之和最大并且每个值各自和不得小于0

思路

想其中一个值看做花费 另一个值看做价值 跑01背包

dp初始化要是很小的值 因为有负值存在所以dp会跑出负值

因为花费也不能为负数 所以扩大100000，打100000当做0花费

对于不同正负价值，有按不同顺序跑，目的实施他们只能加一次

代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
int a[110];
int b[110];
int dp[210000];int main()
{int n;while(scanf("%d",&n)!=EOF){for(int i = 1;i <= n;i++){scanf("%d%d",&a[i],&b[i]);}for(int i = 0;i <= 200000;i++) dp[i] = -INF;dp[100000] = 0;for(int i = 1;i <= n;i++){if(a[i] <= 0){for(int j = 0;j <= 200000+a[i];j++){if(dp[j-a[i]] > -INF&&dp[j-a[i]]+b[i] > dp[j]){dp[j] = dp[j-a[i]]+b[i];}}}else{for(int j = 200000;j >= a[i];j--){if(dp[j-a[i]] > -INF&&dp[j-a[i]] +b[i] > dp[j]){dp[j] = dp[j-a[i]]+b[i];}}}}int ans = 0;for(int i = 100000;i <= 200000;i++){if(dp[i] >= 0&&i-100000+dp[i] > ans){ans = i - 100000 + dp[i];}}printf("%d\n",ans);}return 0;
}