链接：http://acm.ocrosoft.com/problem.php?cid=2001&pid=5

题目描述

  现有N个物品，第i个物品有两个属性A_i和B_i。在其中选取若干个物品，使得sum{A_i  +  B_i}最大，同时sum{A_i}，sum{B_i}均非负（sum{}表示求和）。

输入

        第一行，一个整数，表示物品个数N。         接下来N行，每行两个整数，表示A_i和B_i。

输出

一个整数，表示最大的sum{A_i  +  B_i}。

样例输入

5
-5 7
8 -6
6 -3
2 1
-8 -5

样例输出

8

提示

  N  < =  100  ,  |A_i|  < =  1000  ,  |B_i|  < =  1000

思路：

枚举a_i,dpb_i,

状态转移方程：dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i].x]+a[i].y);

题解：

#include<bits/stdc++.h>
using namespace std;
int n,dp[102][200002],sum=-1e9+7;//sum记录最终答案 
struct node{
	int x,y;
}a[102];
int main()
{
	//之所以以100000和200000为界值，是因为数据范围是正负100*1000，要枚举就要包含整个范围 
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&a[i].x,&a[i].y);
	}
	memset(dp,-127,sizeof(dp));//赋初值相当于一个很小的负数 
	dp[0][100000]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=200000;j>=0;j--)//枚举x变量 
		dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i].x]+a[i].y);//用dp状态转移方程表示y变量 
	}
	
	for(int i=100000;i<=200000;i++)//枚举x满足条件的情况 
	{
		if(dp[n][i]>=0)//当y满足条件的时候 
		sum=max(sum,dp[n][i]+i-100000);//取最大 
	}
	cout<<sum;
	return 0;
}