给你n只奶牛，每只奶牛有两个属性值，分别是聪明值S和有趣值F，并且这些值存在负数，我们需要选取k只牛使得他们的聪明值和兴趣值的和最大，并且要保证TS = S_1 + S_2 + S_3 + …… + S_n（也就是聪明值的和） >= 0， TF = F_1 + F_2 + F_3 + ……+ F_n（也就是有趣值的和） >= 0。这个时候再使得TS+TF最大。
5 -5 7 8 -6 6 -3 2 1 -8 -5
8
典型的01背包问题的变形，这题使我对01背包的问题理解更加深刻。其实我原来写这题的时候想的是一个二维费用背包，将这个背包的容量视为无限大，能装进所有物品，然后保证TS+TF最大，不过后来我发现如果使用二维的话，他们的数据范围是再-100000到100000之间的，如果使用二维的话空间老早就报掉了，所以后来又看了题解发现这是个鬼的二维费用背包，其实就是一个01背包的变形，我们完全可以将S_i视为物品的重量，F_i视为物品的价值，为什么可以这么看呢？因为我们知道01背包求的是使物品的价值总量最大，而这个时候可以知道这个包已经放不下其他物品了，那么其中的物品重量是不是也达到了最大，正是因为如此，我们可以知道01背包是可以让价值和重量都能达到最大的一个算法，再根据之前所说将背包容量视为无限大，数据范围是-100000到100000之间，我们可以将原点右移100000位，使得数据范围移到0至200000，就可以解决负数的问题，但要注意一个地方当s[i]>0的时候倒着枚举做普通的零一背包，如果当s[i]<0的时候就得正着枚举了，因为s[i]+v < v。最后扫描一遍就好。
代码如下：
/************************************************************************* > File Name: Cow_Exhibition.cpp > Author: Frade > Mail: frade@vip.sina.com.cn > Created Time: 2017年05月06日 星期六 09时43分38秒 ************************************************************************/ #include <iostream> #include <cstdio> using namespace std; int Getint() { char c = getchar(); bool flag = false; int ans = 0; while(c != '-' && (c <'0' || c > '9'))c = getchar(); if(c == '-')flag = true,c = getchar(); while(c >= '0' && c <= '9')ans = ans*10 + c - '0',c = getchar(); return (flag == true) ? -ans : ans; } const int maxn = 1000 + 2; const int maxV = 200000; const int INF = 0x3f3f3f3f; int dp[maxV+10]; int v[maxn],u[maxn]; int main() { int n = Getint(); for(int i = 0;i < n; i++)v[i] = Getint(),u[i] = Getint(); for(int i = 0;i <= maxV; i++)dp[i] = -INF; dp[100000] = 0; for(int i = 0;i < n; i++) { if(v[i] > 0) { for(int j = maxV;j >= v[i]; j--) dp[j] = max(dp[j],dp[j-v[i]]+u[i]); } else { for(int j = 0;j <= maxV+v[i]; j++) dp[j] = max(dp[j],dp[j-v[i]]+u[i]); } } int ans = 0; for(int i = 100000;i <= maxV; i++)if(dp[i] > 0)ans = max(ans,dp[i]+i-100000); printf("%d\n",ans); return 0; }