Đề bài
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ụ
Đầ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.
Đầ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.