三星 R&D 现场OA 2025

Viewed 45

面试题目如下:

给定 N 瓶药瓶,M 个容器。每个容器有一个定义好的装载能力 W[i](即最多可装 W[i] 瓶药)。

送运车每次只能装 1 或 2 个容器达医院,但是容器可重复使用。

请你计算最少需要多少次送运,能尽快送完 N 瓶药。如果无法送完,请输出 -1


限制

  • 1 <= N, M, W[i] <= 1000
  • W.length == M

示例

Example 1

N = 5, M = 2
W = [1, 3]
Output: 2

说明:可送 (1+3)=4 和 (1) 或 (3+1) + (1)

Example 2

N = 6, M = 2
W = [4, 5]
Output: -1

说明:最多只能送 5 瓶,不能覆盖 6

Example 3

N = 720, M = 5
W = [27, 52, 119, 144, 124]
Output: 5

说明:最佳配置下能用5次完成送运


一开始我考虑了 2D / 3D 动态规划 (DP),但是最终遇到 TLE 问题
该题相当于“可重复利用的大容量背包” + 单次车载量上限,应该有更好的优化解法
希望同样面试过的同学能一起分享思路,互相促进!

0 Answers
Related Experiences