[leetcode/lintcode 题解] 阿里算法面试真题：高效作业处理服务

描述
Twitter正在测试一种名为Pigeon的新工作处理服务。
Pigeon处理任何任务的时间是任务实际持续时间的两倍，并且每个任务都有一个权重。 此外，Pigeon在一个小时内只能服务一个有限的持续时间（最大运行时间）。
给定Pigon服务的最大运行时间，任务的实际运行时间和权重，确定Pigon服务在一小时内可以实现的最大总权重。
输入包括以下参数：

n: 任务数量weights: 每个任务的权重tasks: 每个任务实际持续时间p: Pigeon一小时的最大运行时间1≤n≤10^31≤weights[i]≤10^61≤tasks[i]≤1001≤p≤10^3

每个任务只能被执行一次。

在线评测地址：领扣题库官网

样例1
[2,4,4,5]
[2,2,3,4]
你可以运行0、1、2号任务，将花费2 * (2 + 2 + 3) = 14 分钟并获得 2 + 4 + 4 = 10 权重。

样例2
[3,2,2]
[3,2,2]
你可以运行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 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

本文转自网络，原文链接：https://developer.aliyun.com/article/783728
本站部分内容转载于网络，版权归原作者所有，转载之目的在于传播更多优秀技术内容，如有侵权请联系QQ/微信：153890879删除，谢谢！