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

描述
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