Cow Exhibition

poj2184:http://poj.org/problem?id=2184

题意：给你n头牛，每头牛有一个S值和一个F值，现在的问题是，要你选出其中的一些牛求出S+T的最大值。但是要保证总的s>=0和F>=0
题解：可以把s作为体积，然后利用0,1背包。求出每个s做对应的最大的F值，然后for一遍，求出最大的f+s。因为有负的值出现，所以把 背包的容量加上一个100000；因为过程中s的值可以是小于0的，for的时候从100000开始即可，不是很好理解。

 #include<stdio.h>

 #include<iostream>

 #include<string.h>

 #include<algorithm>

 using namespace std;

 const int INF=0x3f3f3f3f;

 const int MAXN=;

 int dp[];

 int value[MAXN];

 int weight[MAXN];

 int nKind;

 int main()

 {

     int k=;

     while(scanf("%d",&nKind)!=EOF){

         for(int i=;i<nKind;i++){

             scanf("%d%d",&value[i],&weight[i]);

         }

         for(int i=;i<=;i++)dp[i]=-INF;

         dp[k]=;

         for(int i=;i<nKind;i++){

             if(value[i]>)//正的是逆序

         {

                 for(int j=;j>=value[i];j--)//注意范围

                   if(dp[j-value[i]]>-INF)

                     dp[j]=max(dp[j],dp[j-value[i]]+weight[i]);

             }

             else//负的是顺序

             {

                 for(int j=;j<=+value[i];j++)//注意范围

                   if(dp[j-value[i]]>-INF)

                     dp[j]=max(dp[j],dp[j-value[i]]+weight[i]);

             }

         }

         int ans=;

         for(int i=;i<=;i++)

             if(dp[i]>=&&dp[i]+i->ans)

                 ans=dp[i]+i-;

         printf("%d\n",ans);

     }

     return ;

 }