💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

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

🍥 有很多套卷，每套卷子有 0/1/2 道编程题，题目内容不一定相同，这样 选择题、填空、问答 的比重就占很大了。

🌈 原题题目描述有点怪，本质其实就是01背包。

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

问题描述

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

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

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

输入格式

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

第二行包含 个整数，表示每件物品的重量。

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

输出格式

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

样例输入

2 3
5 5 12
3 1 1

样例输出

12

数据范围

• 
• 物品重量
• 运输距离

题解

这个问题是一个 0-1 背包问题的变种。

定义 表示使用 单位电量能够运输的最大物品重量。对于每件物品，我们可以选择运输或不运输。

状态转移方程为：

其中 和 分别表示第 件物品的重量和运输距离。

我们需要从大到小遍历电量，以避免重复选择同一件物品。最终， 就是我们要求的答案。

时间复杂度：，其中 是物品数量。 空间复杂度：。

参考代码

• Python

def max_load(n, weights, distances):
    # 初始化动态规划数组
    dp = [0] * 39
    
    # 遍历每件物品
    for i in range(n):
        # 从大到小遍历电量
        for j in range(38, weights[i] * distances[i] - 1, -1):
            # 更新状态
            dp[j] = max(dp[j], dp[j - weights[i] * distances[i]] + weights[i])
    
    # 返回最大装载量
    return dp[38]

# 读取输入
_, n = map(int, input().split())
weights = list(map(int, input().split()))
distances = list(map(int, input().split()))