Đề bài
Mỗi người phải đi đúng một lần. Bất kỳ nhóm nào cũng có thể đi cùng nhau nếu tổng trọng lượng của họ không vượt quá capacity. Có thể nhóm lại tự do; thứ tự đầu vào không quan trọng. Hãy tối thiểu hóa số chuyến đi.
Cài đặt hàm elevator_rides(weights, capacity).
Đầu vào
weights: Trọng lượng của từng người.
capacity: Tổng trọng lượng tối đa cho mỗi chuyến đi.
Đầu ra
Trả về số chuyến đi tối thiểu.
Ràng buộc
1 ≤ số người ≤ 20. 1 ≤ capacity ≤ 1.000.000.000. Mỗi trọng lượng nằm trong khoảng từ 1 đến 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
Gửi 3 + 4 cùng nhau và 5 đi riêng. Tổng trọng lượng 12 không thể đi trong một chuyến với sức chứa 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
Cả ba người đều đi cùng nhau được vì 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
Vì số người nhỏ, hãy xét theo tập con thay vì từng chuyến riêng lẻ.
Gợi ý 2
Theo dõi cả số chuyến đã dùng lẫn độ đầy của chuyến cuối cho mỗi tập con.
Gợi ý 3
Khi hai trạng thái dùng cùng số chuyến, hãy ưu tiên trạng thái có tải hiện tại nhỏ hơn.
Độ phức tạp mong đợi
thời gian O(2^n * n), bộ nhớ phụ O(2^n)
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.