这是又是一道01背包的变体，题目要求选出一些牛，使smartness和funness值的和最大，而这些牛有些smartness或funness的值是负的，还要求最终的smartness之和以及funness之和不能为负。

　　这道题的关键有两点：一是将smartness看作花费、将funness看作价值，从而转化为01背包；二是对负值的处理，引入一个DELTA来表示“0”，这里的DELTA一定要大于每一个smartness的绝对值，另外在遍历cost[]的时候如果cost[i]>0，显然时从开的数组的最大值MAX_LMT开始往下减，如果cost[i]<0，则是从0（是0，不是DELTA）开始往上增加。大于0的情况容易想到，小于0的情况比较费解，需要仔细思考。

　　考虑只有一只牛，它的smartness为-x(x>0)，funness为y(y>0),由于将dp[DELTA]赋初值为0，其它的dp[]赋初值为负无穷，所以有dp[DELTA-(-x)]+y>dp[DELTA],即dp[x]会被赋为dp[DELTA-(-x)]+y即y（ dp[x]=max(dp[DELTA-(-x)]+y,dp[DELTA])  ），由于x小于DELTA，所以在最后遍历最大值的时候，这个值根本不会被遍历。

　　再考虑前面已经有一些牛，此时dp[DELTA+x]=y(x>0,y>0)现在出现了一只为-a b(a>0,b>0)的牛，那么dp[DELTA+X-a]会被赋为dp[DELTA+x-a-(-a)]+b=dp[DELTA+x]+b=y+b;最终遍历的时候，如果取最后一只牛，和为x-a+y+b,如果不取，和为x+y,所以最大值究竟是谁取决于b-a的正负。

　　综上所述，这是一种满足题目要求的方法，所以在cost[i]<0的时候时从0开始往上增加。

#include
     
      #include
      
       #define INF 1000000#define MAX_LMT 210000#define MAX_N 110#define DELTA 10000int max(int,int);int main(){    int n,cost[MAX_N],val[MAX_N],dp[MAX_LMT];    while(scanf("%d",&n)!=EOF)    {    int i,j;    for(i=1;i<=n;i++)    {        scanf("%d%d",&cost[i],&val[i]);    }    for(i=0;i
       
        0)        {        for(j=MAX_LMT;j>=cost[i];j--)        {            dp[j]=max(dp[j-cost[i]]+val[i],dp[j]);        }        }        else        {        for(j=0;j
        
         0&&(i-DELTA+dp[i]>ans))        {        ans=i+dp[i]-DELTA;        }    }    printf("%d\n",ans);    }    return 0;}int max(int x,int y){    return x>y?x:y;}