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; }