POJ 2184 Cow Exhibition 背包问题

题意：有一些奶牛，他们有一定的s值和f值，这些值有正有负，最后让保证s的和为非负且f的和为非负的情况下，s+f的最大值。
思路：背包问题，我们可以设dp[i][s]为前i头牛的s值为s时f的最大值，这就转化成了背包问题，即把s当成是体积，f当成是价值，而且可以成功的把二维转化成一维。又因为有负数的情况，所以我们可以都加上一个值，全部转化为正数。在处理负数的时候，循环顺序需要改变一下，一个是01背包，一个是完全背包。即一个倒着循环，一个正着循环，最后取最大值即可。
代码：
[cpp]
//2184 
#include <iostream> 
#include <cstdio> 
#include <string.h> 
#include <climits> 
using namespace std; 
 
#define CLR(arr,val) memset(arr,val,sizeof(arr)) 
const int N = 110; 
const int M = 100005; 
struct cow{ 
    int s,f; 
}cc[N]; 
int dp[2*M]; 
int max(int a,int b){ 
    return a>b?a:b; 
} 
int main(){ 
    //freopen("1.txt","r",stdin); 
    int n; 
    while(scanf("%d",&n) != EOF){ 
        for(int i = 0; i < n; ++i){ 
          scanf("%d%d",&cc[i].s,&cc[i].f); 
        } 
        for(int i = 0; i < 2 * M ;++i) 
            dp[i] = INT_MIN; 
        dp[100000] = 0; 
        for(int i = 0; i < n; ++i){ 
            if(cc[i].s >= 0){ 
                for(int j = 2*M-1; j >= cc[i].s; --j){ 
                    if(dp[j - cc[i].s] > INT_MIN) 
                         dp[j] = max(dp[j],dp[j - cc[i].s] + cc[i].f); 
                } 
            } 
            else{ 
                for(int j = cc[i].s; j - cc[i].s < 2*M; ++j){ 
                    if(dp[j - cc[i].s] > INT_MIN) 
                        dp[j] = max(dp[j],dp[j - cc[i].s] + cc[i].f); 
                } 
            } 
        } 
        int ans = INT_MIN; 
        for(int i = 100000; i < 2*M; ++i){ 
            if(dp[i] >= 0) 
               ans = max(ans,dp[i] + i - 100000); 
        } 
        printf("%d/n",ans); 
    } 
    return 0; 
} 
作者：wmn_wmn