描述
Twitter正在测试一种名为Pigeon的新工作处理服务。
Pigeon处理任何任务的时间是任务实际持续时间的两倍，并且每个任务都有一个权重。 此外，Pigeon在一个小时内只能服务一个有限的持续时间（最大运行时间）。
给定Pigon服务的最大运行时间，任务的实际运行时间和权重，确定Pigon服务在一小时内可以实现的最大总权重。
输入包括以下参数：
- n: 任务数量
- weights: 每个任务的权重
- tasks: 每个任务实际持续时间
- p: Pigeon一小时的最大运行时间
- 1≤n≤10^3
- 1≤weights[i]≤10^6
- 1≤tasks[i]≤100
- 1≤p≤10^3
每个任务只能被执行一次。
在线评测地址：领扣题库官网
样例1
输入:
4
[2,4,4,5]
[2,2,3,4]
15
输出:
10
说明:
你可以运行0、1、2号任务，将花费2 * (2 + 2 + 3) = 14 分钟并获得 2 + 4 + 4 = 10 权重。样例2
输入:
3
[3,2,2]
[3,2,2]
9
输出:
4
说明:
你可以运行1、2号任务，将花费2 * (2 + 2) = 8 分钟并获得 2 + 2 = 4 权重。考虑01背包进行求解，将p除2是总容量，每个人物的时间是他需要的容量，价值为权重
代码
public class Solution {
/**
* @param n: the number of tasks
* @param weights: the weight for every task
* @param tasks: the actual duration of every task
* @param p: maximum runtime for Pigeon in an hour
* @return: the maximum total weight that the Pigeon service can achieve in an hour
*/
public int maxWeight(int n, int[] weights, int[] tasks, int p) {
// write your code here
int[][] dp = new int[n + 1][p / 2 + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= p / 2; j++) {
if (j < tasks[i - 1]) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - tasks[i - 1]] + weights[i - 1]);
}
}
}
return dp[n][p / 2];
}
}更多题解参考：九章官网solution
