✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题（建议用时：90分钟/套）
• 对照解析查漏补缺

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

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

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

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

题目一：微型仓储机器人的最大装载量

1️⃣：识别为 0-1 背包问题，背包容量为 38 单位电量

2️⃣：每件物品的"重量"为物品重量×距离，"价值"为物品重量

3️⃣：使用一维动态规划，倒序遍历避免重复选择

难度：中等

这道题目的关键在于将实际问题抽象为经典的 0-1 背包模型。通过理解耗电量的计算方式和目标函数，可以快速转化为动态规划问题。核心技巧是正确定义状态和合理设置遍历顺序。

01. 微型仓储机器人的最大装载量

问题描述

K 小姐正在开发一款微型仓储机器人。这款机器人配备了一块容量为 38 单位电量的微型电池，用于执行仓库内的物品运输任务。机器人的耗电量与运输物品的重量和运输距离成正比，每单位重量每单位距离的耗电量为 1 单位电量。

现在，仓库管理系统收到了 件物品的运输请求，每件物品都有其特定的重量和需要运输的距离。K 小姐希望能够计算出在一次充电周期内，这款微型仓储机器人能够运输的最大物品重量。

你的任务是编写一个程序，帮助 K 小姐确定机器人在一次充电周期内能够运输的最大物品重量。

输入格式

第一行包含两个整数 和 ，其中 可以忽略， 表示需要运输的物品数量。

第二行包含 个空格分开的正整数，表示每件物品的重量。

第三行包含 个空格分开的正整数，表示每件物品需要运输的距离。

输出格式

输出一个整数，表示机器人在一次充电周期内能够运输的最大物品重量。如果无法运输任何物品，则输出 0。

样例输入

2 3
5 5 12
3 1 1

样例输出

12

数据范围

• 
• 物品重量
• 运输距离

样例	解释说明
样例1	有 3 件物品：重量分别为 ，距离分别为 。第一件物品耗电 ，第二件物品耗电 ，第三件物品耗电 。在 38 单位电量下，可以选择第二件和第三件物品，总重量为 ，但最优解是只选择第三件物品，重量为 12。

题解

这道题本质上是一个 0-1 背包问题。每件物品的"重量"（占用的容量）是 重量 × 距离，"价值"是物品的重量，背包容量是 38 单位电量。

关键观察：

1. 每件物品要么选择运输，要么不运输（0-1 背包）
2. 每件物品消耗的电量 = 物品重量 × 运输距离
3. 目标是在电量限制下最大化运输的总重量

算法思路：

1. 使用一维动态规划数组 dp[j] 表示使用 j 单位电量能运输的最大重量
2. 对每件物品，从电量上限向下遍历，避免重复选择
3. 状态转移：dp[j] = max(dp[j], dp[j-cost] + weight)，其中 cost = weight × distance

具体步骤：

1. 初始化 dp 数组，dp[0] = 0，其余为 0
2. 对于每件物品 i，从 j = 38 向下遍历到 cost[i]
3. 更新 dp[j] = max(dp[j], dp[j-cost[i]] + weight[i])
4. 最终答案是 dp[38]

为什么要倒序遍历？因为正序遍历会导致一个物品被重复选择多次。

时间复杂度：，其中 N 是物品数量。 空间复杂度：，使用一维数组优化空间。

对于给定的数据范围，这个复杂度完全可以接受。

参考代码

• Python

import sys
input = lambda: sys.stdin.rea