251巧克力板选择问题

题解

题目要求在多个背包的承重限制下，计算每个背包中最多可以携带的巧克力板数量。每块巧克力板的重量为其边长的平方。需要为每个背包找到在不超过其最大承重的情况下，能够携带的最多巧克力板数。

思路分析

1. 动态规划（01 背包）：

   • 对于每个背包，使用动态规划来计算在承重限制下可以携带的最大巧克力板数。
   • 状态 f[j] 表示在承重 j 下可以携带的最大巧克力板数。

2. 状态转移：

   • 遍历每块巧克力板，重量为 x^2。
   • 对于每个背包容量 j 从大到小遍历：
     • 如果选择当前巧克力板，则 f[j] = max(f[j], f[j - x^2] + 1)。

3. 优化：

   • 计算所有查询中的最大承重 vol，并初始化动态规划数组 f。
   • 最终对于每个查询，直接返回对应的 f[q]。

代码解析

def solution(n: int, m: int, a: list, queries: list) -> list:
    vol = max(queries)
    f = [0] * (vol + 1)
    for x in a:
        for j in range(vol, x ** 2 - 1, -1):
            f[j] = max(f[j], f[j - x ** 2] + 1)
    return [f[q] for q in queries]

if __name__ == '__main__':
    print(solution(5, 5, [1, 2, 2, 4, 5], [1, 3, 7, 9, 15]) == [1, 1, 2, 3, 3])
    print(solution(4, 3, [3, 1, 2, 5], [5, 10, 20]) == [2, 2, 3])
    print(solution(6, 4, [1, 3, 2, 2, 4, 6], [8, 12, 18, 25]) == [2, 3, 4, 4])

复杂度分析

• 时间复杂度：$O(nvol)$，其中 n 是巧克力板的数量，vol 是最大承重。
• 空间复杂度：$O(vol)$，使用了一维数组 f 来存储状态。