目录

题目

思路

Code

题目

某部门的项目经理，近期手头有n个开发任务必须全部完成(不可并行，必须顺序执行)。每个任务有三个属性:
·持续时间duration[i]:执行该任务需要的时间;
·截止时间deadline[i]:任务必须在某个时刻前完成才能获得收益;
收益profit[i]:若在截止时间前完成，可获得的收益。任务从时刻0开始依次执行。若任务i的完成时刻(即开始时刻+duration[i])≤deadline[i])，则你获得profit[i];否则该任务收益为0(任务仍要执行)。他可以任意决定任务的执行顺序，目标是最大化所有任务的总收益。请帮他计算最大可能收益。
输入描述
共有4个输入参数:
1.n:任务数量(1≤n≤20)，编号0到n-1。
2.duration:长度为n 的正整数数组,duration[i]≤1000.
3.deadline:长度为n 的正整数数组,deadline|i]≤1000.
4.profit:长度为n的正整数数组，profit[i]≤1000。
输出描述
输出一个整数，表示能获得的最大总收益。

样例1

输入

3
2,1,3
3,2,5
10,20,30

输出

50
说明

按顺序任务2>任务3>任务1执行:
·任务2:时刻0开始，持续1，完成于时刻1≤2，收益20;
·任务3:时刻1开始，持续3，完成于时刻4≤5，收益30;
任务1:时刻4开始，持续2,完成于时刻6>3,收益0。总收益=20+30+0=50，此为最大。
样例2

输入

4
1,2,3,4
1,3,6,10
100,200,300,400

输出

1000

思路

状态压缩 DP

核心观察

对于任意一个已选任务集合 `mask`，无论这些任务以什么顺序执行，**总耗时是固定的**（等于所有 duration 之和）。因此，在 `mask` 之后加一个新任务时，这个新任务的完成时间也是确定的，跟 `mask` 内部的顺序无关。

这就意味着：我们只需要关心"已经做了哪些任务"，不需要关心"具体是先做谁后做谁"——因为总时间只取决于选了的任务集合，不取决于顺序。

状态定义

`dp[mask]` = 完成了集合 `mask` 中的所有任务，能获得的最大收益

边界

`dp[0] = 0`

转移

枚举 mask 中尚未完成的任务 j，把它放到末尾执行：

- 当前时间 = totalTime[mask]（mask 中所有任务的总耗时）

- 任务 j 的完成时间 = totalTime[mask] + duration[j]

- 新增收益 = profit[j]（如果完成时间 ≤ deadline[j]），否则 0

- `dp[mask | (1<<j)] = max(dp[mask | (1<<j)], dp[mask] + 新增收益)`

正确性证明

对于任意一个任务排列，把它按顺序逐个加入 mask，恰好对应 DP 的一条路径。DP 在每条路径上都取最优，最终 dp[全掩码] 就是全部 n 个任务做完的最大收益。

关键点在于：对于某个 mask，它的总耗时是唯一确定的（duration 之和），所以从 mask 出发加入 j 的完成时间也是唯一确定的——不依赖于 mask 内部的具体执行顺序。因此 DP 不会漏掉任何可能的排列，也不会重复计算。

Code

import sys


def solve(n, duration, deadline, profit):
    """
    任务调度最大收益
    状态压缩 DP：dp[mask] = 完成 mask 中所有任务的最大收益
    """
    # ---- 预处理：计算每种任务子集的总耗时 ----
    # totalTime[mask] = mask 中所有任务的 duration 之和
    totalTime = [0] * (1 << n)
    for mask in range(1, 1 << n):
        # lowbit 技巧：取 mask 最低位的 1，得到对应的任务编号
        lowbit = mask & -mask
        task = (lowbit.bit_length() - 1)  # lowbit = 1<<task
        prev = mask ^ lowbit
        totalTime[mask] = totalTime[prev] + duration[task]

    # ---- DP ----
    dp = [0] * (1 << n)

    for mask in range(1 << n):
        curTime = totalTime[mask]
        # 尝试将每个尚未完成的任务 j 添加到末尾
        for j in range(n):
            if mask >> j & 1:  # j 已完成，跳过
                continue
            newMask = mask | (1 << j)
            # 任务 j 的完成时间 = curTime + duration[j]
            finishTime = curTime + duration[j]
            addProfit = profit[j] if finishTime <= deadline[j] else 0
            cand = dp[mask] + addProfit
            if cand > dp[newMask]:
                dp[newMask] = cand

    return dp[(1 << n) - 1]


def main():
    try:
        n_line = sys.stdin.readline()
        if not n_line:
            return
        n = int(n_line.strip())
        duration = list(map(int, sys.stdin.readline().strip().split(',')))
        deadline = list(map(int, sys.stdin.readline().strip().split(',')))
        profit = list(map(int, sys.stdin.readline().strip().split(',')))
        print(solve(n, duration, deadline, profit))
    except Exception:
        print(0)


if __name__ == "__main__":
    main()

JS

const readline = require('readline');

/**
 * 任务调度最大收益
 * @param {number} n         任务数量
 * @param {number[]} duration 持续时间数组
 * @param {number[]} deadline 截止时间数组
 * @param {number[]} profit   收益数组
 * @returns {number} 最大总收益
 */
function solve(n, duration, deadline, profit) {
    const totalMasks = 1 << n;

    // ---- 预处理：每种任务子集的总耗时 ----
    const totalTime = new Array(totalMasks).fill(0);
    for (let mask = 1; mask < totalMasks; mask++) {
        const lowbit = mask & -mask;
        // lowbit 对应 2^task，用位运算求 task 编号
        const task = Math.log2(lowbit);
        const prev = mask ^ lowbit;
        totalTime[mask] = totalTime[prev] + duration[task];
    }

    // ---- DP ----
    const dp = new Array(totalMasks).fill(0);

    for (let mask = 0; mask < totalMasks; mask++) {
        const curTime = totalTime[mask];
        for (let j = 0; j < n; j++) {
            if (mask >> j & 1) continue;  // j 已完成
            const newMask = mask | (1 << j);
            const finishTime = curTime + duration[j];
            const addProfit = finishTime <= deadline[j] ? profit[j] : 0;
            const cand = dp[mask] + addProfit;
            if (cand > dp[newMask]) dp[newMask] = cand;
        }
    }

    return dp[totalMasks - 1];
}

// ---- 主程序 ----
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let lineCount = 0;
let n, duration, deadline, profit;

rl.on('line', (line) => {
    try {
        line = line.trim();
        if (lineCount === 0) {
            n = parseInt(line, 10);
            lineCount++;
        } else if (lineCount === 1) {
            duration = line.split(',').map(Number);
            lineCount++;
        } else if (lineCount === 2) {
            deadline = line.split(',').map(Number);
            lineCount++;
        } else if (lineCount === 3) {
            profit = line.split(',').map(Number);
            console.log(solve(n, duration, deadline, profit));
            rl.close();
        }
    } catch (e) {
        console.log(0);
        rl.close();
    }
});

【华为od机试真题Python+JS+Java+Go合集】【超值优惠】：Py/JS/Java/Go合集

【华为od机试真题Python】：Python真题题库

【华为od机试真题JavaScript】：JavaScript真题题库

【华为od机试真题Java&Go】：Java&Go真题题库

【华为od机试真题C++】：C++真题题库

【华为od机试真题C语言】：C语言真题题库

【华为od面试手撕代码题库】：面试手撕代码题库

【华为od机试面试交流群】【文章底部有二维码链接，可扫码加交流群】

华为OD机试:二本院校有机会吗?
有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。