题目描述
贝西有 ( N )（( 1 \leq N \leq 100 )）头牛，每头牛有两个属性：
- 聪明度 ( S_i )（( -1000 \leq S_i \leq 1000 )）
- 趣味性 ( F_i )（( -1000 \leq F_i \leq 1000 )）
她要选一些牛去参加展览。对于选出的牛的集合，定义：
- 总聪明度 ( TS ) = 所有选中牛的 ( S_i ) 之和
- 总趣味性 ( TF ) = 所有选中牛的 ( F_i ) 之和
她希望在 ( TS ) 与 ( TF ) 都 ≥ 0 的条件下，最大化 ( TS + TF ) 的值。
如果没有任何一个子集能使 ( TS ) 与 ( TF ) 同时非负，输出 0。
输入格式
第 1 行：整数 ( N )
第 2..N+1 行：每行两个整数 ( S_i, F_i )
输出格式
一个整数：满足条件的最大的 ( TS + TF )
样例
输入
5
-5 7
8 -6
6 -3
2 1
-8 -5
输出
8
解释
选牛 1、3、4：
( TS = -5 + 6 + 2 = 3 )
( TF = 7 - 3 + 1 = 5 )
( TS + TF = 8 )
解题思路
目标：贝西想要最大化 TS 和 TF 的总和
F[s][f]=1 ,奶牛的子集得到 聪明值为s，趣味值为f。
转换为 F[s] , 奶牛的子集得到 聪明值为s时，获得最大的趣味值为F[s]。
F[v] ,趣味值为v是最大趣味值为F[v],F[v]=max(F[v-s_i]+f_i,F[v])
实现细节：
-
F[V], 出现 \(V<0\) 如何处理
将F[V]数组整体移动 \(T\) 单位，\(T=100 \times 1000\) -
s[i]<0处理，分类讨论。
\(s[i]>0\)，背包的有效空间：\([s[i],2 \times T]\) ；s[i]<0, 背包的有效空间为 \([0, 2\times T+s[i] ]\) -
求答案是必须保证聪明值和趣味值均为正数。
-
初始化需要处理，F[T]=0,表示聪明值为0时，最大趣味值为0，其他为无效状态-INF。
#include <iostream>
#define LL long long
using namespace std;
int n;
int s[1002],f[1002],F[200002];
const int INF=0x3f3f3f3f;int main() {while (scanf("%d",&n)==1) {int sum=0;for (int i=1;i<=n;i++) cin>>s[i]>>f[i],sum+=s[i];int T=100000;int k=1;for (int i=0;i<=2*T;i++) F[i]=-INF;F[T]=0;for (int i=1;i<=n;i++) {if (s[i]>0){for (int j=2*T;j>=s[i];j--)if (F[j-s[i]]>-INF) F[j]=max(F[j],F[j-s[i]]+f[i]);}if (s[i]<0){for(int j=0;j<=2*T+s[i];j++)if (F[j-s[i]]>-INF)F[j]=max(F[j],F[j-s[i]]+f[i]);}}int Ans=0;for (int j=T;j<=T+T;j++)if (F[j]>0)Ans=max(Ans,F[j]+j-T);cout<<Ans<<endl;}return 0;
}