✅ 秋招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线180+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

京东-2025.11.08

题目一：小兰的任务分配

1️⃣：使用动态规划，状态定义为完成任务数和使用外包券数

2️⃣：枚举每个任务的两种完成方式进行状态转移

3️⃣：从最多任务数开始查找满足精力值限制的最优方案

难度：中等

题目二：机械臂的路径规划

1️⃣：扩展BFS状态，增加下一步移动方向的维度

2️⃣：根据当前状态的方向限制进行状态转移

3️⃣：使用BFS求解最短路径问题

难度：中等

1. 小兰的任务分配

问题描述

小兰是一家项目管理公司的负责人，现在她手上有 个任务需要在今天完成。每个任务都可以通过两种方式完成：

• 自己亲自完成（需要消耗一定的精力值）

• 委托给专业团队完成（需要消耗较少的精力值，但需要使用一张外包券）

小兰当前拥有 点精力值和 张外包券。她希望在优先完成尽可能多任务的前提下，让自己的精力消耗最小化。

请你帮助小兰计算，她最多能完成多少个任务，以及在完成这么多任务的情况下，最少需要消耗多少精力值。

输入格式

第一行包含三个整数 ，分别表示任务数量、小兰拥有的精力值以及外包券数量。

接下来 行，每行两个整数 ，表示第 个任务如果自己完成需要消耗 点精力值，如果委托完成需要消耗 点精力值。

输出格式

输出一行，包含两个整数，用空格分隔，分别表示小兰最多可以完成的任务数量，以及在完成这么多任务的情况下的最小精力消耗。

样例输入

3 20 1
8 5
7 4
10 6

4 25 2
10 6
8 5
12 7
9 6

样例输出

2 12

3 20

数据范围

题解

这道题的核心在于，我们需要在精力值和外包券的双重约束下，尽可能完成更多任务，并且在任务数量相同时选择精力消耗最小的方案。

解题思路

这是一个典型的背包类动态规划问题。我们定义状态 表示完成了 个任务且使用了 张外包券时，所需的最小精力值。

初始状态：，表示完成0个任务且不使用外包券时精力消耗为0，其余状态初始化为无穷大。

状态转移：对于每个任务，我们有两种选择：

1. 自己完成：从状态 转移到 ，精力值增加
2. 委托完成：从状态 转移到 ，精力值增加

为了避免重复计算，我们对每个任务按照倒序更新状态。

最后，我们从完成任务数最多的状态开始查找，找到第一个精力消耗不超过 且使用外包券不超过 的状态，这就是答案。

时间复杂度

状态数量为 ，每个任务的转移需要遍历所有状态，总体时间复杂度为 。在题目给定的数据范围内（），这个复杂度是完全可以接受的。

空间复杂度

需要维护一个二维数组 ，空间复杂度为 。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()

def solve():
    # 读入任务数、精力值和外包券数量
    N, X, Y = map(int, input().split())
    tasks = []
    for _ in range(N):
        a, b = map(int, input().split())
        tasks.append((a, b))
    
    # dp[i][j] 表示完成i个任务使用j张外包券的最小精力消耗
    INF = float('inf')
    dp = [[INF] * (Y + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    
    # 枚举每个任务
    for idx in range(N):
        self_cost, outsrc_cost = tasks[idx]
        # 倒序遍历避免重复使用
        for i in range(idx, -1, -1):
            for j in range(Y + 1):
                if dp[i][j] == INF:
                    continue
                # 选择1：自己完成任务
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + self_cost)
                # 选择2：委托完成任务
                if j + 1 <= Y:
                    dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + outsrc_cost)
    
    # 找出最多完成的任务数和对应的最小精力消耗
    ans_cnt, ans_energy = 0, 0
    for i in range(N, -1, -1):
        min_energy = min(dp[i])
        if min_energy <= X:
            ans_cnt = i
            ans_energy = min_energy
            break
    
    print(ans_cnt, ans_energy)

if __name__ == "__main__":
    solve()

• Cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    long long X;
    int Y;
    cin >> N >> X >> Y;
    
    // 存储每个任务的两种完成方式的成本
    vector<long long> self(N), outsrc(N);
    for (int i = 0; i < N; ++i) {
        cin >> self[i] >> outsrc[i];
    }
    
    // dp[i][j]: 完成i个任务使用j张券的最小精力值
    const long long INF = 4e18;
    vector<vector<long long>> dp(N + 1, vector<long long>(Y + 1, INF));
    dp[0][0] = 0;
    
    // 枚举每个任务
    for (int k = 0; k < N; ++k) {
        // 倒序更新状态
        for (int i = k; i >= 0; --i) {
            for (int j = 0; j <= Y; ++j) {
                if (dp[i][j] >= INF) continue;
                // 方式1：自己完成
                if (dp[i + 1][j] > dp[i][j] + self[k]) {
                    dp[i + 1][j] = dp[i][j] + self[k];
                }
                // 方式2：委托完成
                if (j + 1 <= Y && dp[i + 1][j + 1] > dp[i][j] + outsrc[k]) {
                    dp[i + 1][j + 1] = dp[i][j] + outsrc[k];
                }
            }
        }
    }
    
    // 从最多任务数开始查找可行方案
    int max_task = 0;
    long long min_cost = 0;
    for (int i = N; i >= 0; --i) {
        long long cur_min = INF;
        for (int j = 0; j <= Y; ++j) {
            cur_min = min(cur_min, dp[i][j]);
        }
        if (cur_min <= X) {
            max_task = i;
            min_cost = cur_min;
            break;
        }
    }
    
    cout << max_task << ' ' << min_cost << '\n';
    return 0;
}

• Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] firstLine = br.readLine().split(" ");
        int taskNum = Integer.parseInt(firstLine[0]);
        long totalEngy = Long.parseLong(firstLine[1]);
        int ticketNum = Integer.parseInt(firstLine[2]);
        
        // 读取每个任务的成本
        long[] selfCost = new long[taskNum];
        long[] outsrcCost = new long[taskNum];
        for (int i = 0; i < taskNum; i++) {
            String[] line = br.readLine().split(" ");
            selfCost[i] = Long.parseLong(line[0]);
            outsrcCost[i] = Long.parseLong(line[1]);
        }
        
        // dp[i][j]: 完成i个任务用j张券的最小精力
        final long INF = (long) 4e18;
        long[][] dp = new long[taskNum + 1][ticketNum + 1];
        for (int i = 0; i <= taskNum; i++) {
            Arrays.fill(dp[i], INF);
        }
        dp[0][0] = 0;
        
        // 处理每个任务
        for (int idx = 0; idx < taskNum; idx++) {
            // 倒序更新
            for (int i = idx; i >= 0; i--) {
                for (int j = 0; j <= ticketNum; j++) {
                    if (dp[i][j] == INF) continue;
                    // 选项1：自己做
                    dp[i + 1][j] = Math.min(dp[i + 1][j], 
                                           dp[i][j] + selfCost[idx]);
                    // 选项2：外包
                    if (j + 1 <= ticketNum) {
                        dp[i + 1][j + 1] = Math.min(dp[i + 1][j + 1],
                                                     dp[i][j] + outsrcCost[idx]);
                    }
                }
            }
        }
        
        // 查找最优解
        int bestCnt = 0