目录
1 问题描述
问题描述
给n个有序整数对ai bi，你需要选择一些整数对 使得所有你选定的数的ai+bi的和最大。并且要求你选定的数对的ai之和非负，bi之和非负。
输入格式
输入的第一行为n，数对的个数
以下n行每行两个整数 ai bi
以下n行每行两个整数 ai bi
输出格式
输出你选定的数对的ai+bi之和
样例输入
5
-403 -625
-847 901
-624 -708
-293 413
886 709
-403 -625
-847 901
-624 -708
-293 413
886 709
样例输出
1715
数据规模和约定
1<=n<=100
-1000<=ai,bi<=1000
-1000<=ai,bi<=1000
2 解决方案
本题主要考查动态规划思想的运用，下面的具体编码参考自文末参考资料1，我看了一下文中的讲解：
主要核心问题是：题目要求结果中所有ai之和非负，bi的和非负。
那么，首先，对输入数据处理一下，过滤掉所有ai + bi <= 0的数据对，对于剩下的数据对中，从第一个数据对开始，对于前i行数据，依次求取当ai的和从0到200000之间某一个值时，前i行中bi和的最大值。那么当i = n，即最后一行数据时，求取：当dp[i][j] >= 0（PS：bi的和非负）且j >= 100000（PS：ai的和非负），其中的dp[i][j]+j的最大值，即为最终结果。对于200000和100000的定义，详细参考代码注释哦。
有点遗憾的是，下面的代码在系统运行评分为91分...代码仅供参考
具体代码如下：
import java.util.Scanner;
public class Main {
public int[][] dp = new int[105][200005];
public final static int t = 100001; //ai或者bi所有输入项和最大为100*1000 = 100000
public final static int f = -200005; //ai+bi所有输入项和最小为100*-1000*2 = -200000
public int getMax(int a, int b) {
return a > b ? a : b;
}
/*
* dp[i][j]:i表示符合输入数据中ai + bi > 0的前i项，j表示这i项中ai的和
* dp[i][j]：其具体含义为当前i项ai和为j时，存放前i项中bi和的最大值
* 那么，可知共有n项满足ai + bi > 0，那么找出dp[n][j] + j最大值即为最终结果
*/
public void printResult(int[] A, int[] B, int len) {
for(int i = 0;i < len;i++) {
for(int j = -t;j < t;j++)
dp[i][j + t] = f; //初始化为题目所有输入数据和最小值，即前i项中bi的和
}
for(int i = 0;i < len;i++) {
//此处，使用t作为防止数组越界标准数，因为A[i]有可能小于0，而数组下标不可能为负数
dp[i][A[i] + t] = B[i]; //初始化当j = A[i] + t时，此时前i项B的和为B[i]
}
for(int i = 1;i < len;i++) {
for(int j = -t;j < t;j++) {
dp[i][j + t] = getMax(dp[i - 1][j + t], dp[i][j + t]);
if(j + t - A[i] < 0 || j + t - A[i] > 200001)
continue;
//此处判定，作为当j + t中不包含第i项A[i]时，更新当前最大值
dp[i][j + t] = getMax(dp[i][j + t], dp[i - 1][j + t - A[i]] + B[i]);
}
}
int result = f;
for(int i = 0;i < t;i++) {
//可知，最终的dp[i][j]中，其中j >= t，dp[i][j] >= 0，才符合对于sum(ai)和sum(bi)均不小于0的要求
if(dp[len - 1][i + t] >= 0)
result = getMax(result, dp[len - 1][i + t] + i);
}
if(result <= 0) {
System.out.println(0);
return;
}
System.out.println(result);
return;
}
public static void main(String[] args) {
Main test = new Main();
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int len = 1;
int[] A = new int[n + 1];
int[] B = new int[n + 1];
for(int i = 1;i <= n;i++) {
int a = in.nextInt();
int b = in.nextInt();
if(a + b > 0) { //过滤掉所有a + b <= 0的数据对
A[len] = a;
B[len++] = b;
}
}
test.printResult(A, B, len);
}
}
上述错误修正如下：
错误在输入数据处理上：即注释中//过滤掉所有a + b <= 0的数据对，看到文末网友评论，我仔细想了一下数据处理的逻辑，发现如果过滤掉所有a + b<=0的数据对，会过滤掉其中a > 0或者b > 0的情形，导致在求ai的和出现误差，以及bi的和出现误差。（PS:即如果ai+a，其中a > 0，那么遇到下一个数据对时，其可以接纳的数据对就会增加，同理，对于bi也一样。）
现在有两种方案：
（1）把过滤条件修改为如下：if(a < 0 && b < 0) continue;
（2）不对输入数据进行过滤处理，直接计算处理所有输入数据对。
验证结果如下（PS：在蓝桥杯练习系统中评分均为100分）：
修改后代码：
import java.util.Scanner;
public class Main {
public int[][] dp = new int[105][200005];
public final static int t = 100001; //ai或者bi所有输入项和最大为100*1000 = 100000
public final static int f = -200005; //ai+bi所有输入项和最小为100*-1000*2 = -200000
public int getMax(int a, int b) {
return a > b ? a : b;
}
/*
* dp[i][j]:i表示符合输入数据中ai + bi > 0的前i项，j表示这i项中ai的和
* dp[i][j]：其具体含义为当前i项ai和为j时，存放前i项中bi和的最大值
* 那么，可知共有n项满足ai + bi > 0，那么找出dp[n][j] + j最大值即为最终结果
*/
public void printResult(int[] A, int[] B, int len) {
for(int i = 0;i < len;i++) {
for(int j = -t;j < t;j++)
dp[i][j + t] = f; //初始化为题目所有输入数据和最小值，即前i项中bi的和
}
for(int i = 0;i < len;i++) {
//此处，使用t作为防止数组越界标准数，因为A[i]有可能小于0，而数组下标不可能为负数
dp[i][A[i] + t] = B[i]; //初始化当j = A[i] + t时，此时前i项B的和为B[i]
}
for(int i = 1;i < len;i++) {
for(int j = -t;j < t;j++) {
dp[i][j + t] = getMax(dp[i - 1][j + t], dp[i][j + t]);
if(j + t - A[i] < 0 || j + t - A[i] > 200001)
continue;
//此处判定，作为当j + t中不包含第i项A[i]时，更新当前最大值
dp[i][j + t] = getMax(dp[i][j + t], dp[i - 1][j + t - A[i]] + B[i]);
}
}
int result = f;
for(int i = 0;i < t;i++) {
//可知，最终的dp[i][j]中，其中j >= t，dp[i][j] >= 0，才符合对于sum(ai)和sum(bi)均不小于0的要求
if(dp[len - 1][i + t] >= 0)
result = getMax(result, dp[len - 1][i + t] + i);
}
if(result <= 0) {
System.out.println(0);
return;
}
System.out.println(result);
return;
}
public static void main(String[] args) {
Main test = new Main();
Scanner in = new Scanner(System.in);
//System.out.println("请输入：");
int n = in.nextInt();
int len = 1;
int[] A = new int[n + 1];
int[] B = new int[n + 1];
for(int i = 1;i <= n;i++) {
int a = in.nextInt();
int b = in.nextInt();
// if(a < 0 && b < 0)
// continue;
// if(a + b > 0) { //过滤掉所有a + b <= 0的数据对
A[len] = a;
B[len++] = b;
// }
}
test.printResult(A, B, len);
}
}
参考资料：