Khó 1 đã giải Tỷ lệ chấp nhận 100.0%

Minimum Elevator Rides

Group people into as few weight-limited elevator rides as possible.

Bạn sẽ học được gì

  • Represent groups of people as bitmasks
  • Store the best rides and last ride weight per subset
  • Handle exponential search spaces cleverly

Đề bài

Xem bản dịch

Each person must ride exactly once. Any group can share a ride if the sum of its weights is no greater than capacity. People may be regrouped freely; their input order does not matter. Minimize the number of rides.

Implement elevator_rides(weights, capacity).

Input

weights: The weight of each person.

capacity: The maximum combined weight in a ride.

Output

Return the minimum number of rides.

Ràng buộc

1 ≤ people ≤ 20. 1 ≤ capacity ≤ 1,000,000,000. Every weight is between 1 and capacity.

Ví dụ

Ví dụ 1
Đầu vào:
weights = [3, 4, 5]
capacity = 7

Kết quả mong đợi:
expected = 2
Đầu vào:
std::vector<long long> weights = {3, 4, 5};
long long capacity = 7;

Kết quả mong đợi:
long long expected = 2;
Đầu vào:
long[] weights = new long[] {3, 4, 5};
long capacity = 7;

Kết quả mong đợi:
long expected = 2;

Giải thích

Send 3 + 4 together and 5 separately. Total weight 12 cannot fit in one ride of capacity 7.

Ví dụ 2
Đầu vào:
weights = [2, 2, 2]
capacity = 6

Kết quả mong đợi:
expected = 1
Đầu vào:
std::vector<long long> weights = {2, 2, 2};
long long capacity = 6;

Kết quả mong đợi:
long long expected = 1;
Đầu vào:
long[] weights = new long[] {2, 2, 2};
long capacity = 6;

Kết quả mong đợi:
long expected = 1;

Giải thích

All three people fit together because 2 + 2 + 2 = 6.

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Since the number of people is small, consider subsets rather than individual rides.

Gợi ý 2

Track both how many rides are used and how full the current last ride is for each subset.

Gợi ý 3

When two states use the same number of rides, prefer the one with smaller current load.

Độ phức tạp mong đợi

O(2^n * n) time, O(2^n) extra space

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

# Người giải Ngôn ngữ Thời gian Bộ nhớ AI đánh giá Lời giải
1 ННикита Python 831 ms - 4/5 Xem code

Học hỏi từ người khác

Giải pháp cộng đồng

Cảnh báo: Có 1 lời giải đầy đủ bên dưới Hãy thử tự giải trước. Bạn vẫn có thể xem mã của người khác và đánh giá AI. Đăng nhập và giải thử thách để tham gia thảo luận.