Bài tập Code contest, dynamic programming, training Dumv 20/03/2025 0 Comments

orderConsignment

Có n khách hàng đang xếp hàng để gửi hàng ở bưu cục CL. Chi phí vận chuyển mà bưu cục nhận cho từng món hàng của từng người là a₀, a₁, ..., a_n-1. Đối với mỗi người tới gửi hàng, nhân viên cần đúng 1 phút để hoàn tất hồ sơ cho người đó. Các khách hàng là những người rất bận và họ chỉ có thể chờ trong một khoảng thời gian nào đó, nếu quá thời gian thì họ sẽ không gửi hàng nữa. Thời gian mà mỗi khách hàng chờ đợi được là t₀, t₁, ..., t_n-1 (tính theo phút). Chủ bưu cục là một nguời tham lam, ông ta luôn muốn làm sao để nhận được nhiều tiền nhất. Bạn hãy giúp nhân viên chọn ra thứ tự gửi hàng cho các khách hàng sao cho số tiền bưu cục nhận được là nhiều nhất có thể (có thể từ chối những khách hàng nào đó vì lợi nhuận)

Ví dụ

Với a = [10, 20, 5, 12], t = [2, 3, 3, 1] thì kết quả là orderConsignment(a, t) = 42.
Giải thích: nhìn vào mảng t có thể thấy bưu cục chỉ có thể phục vụ được cho tối đa 3 người, trong trong đó người thứ 3 là người có chi phí vận chuyển ít nhất nên bưu cục sẽ từ chối phục vụ người này. Vậy thứ tự phục vụ để bưu cục nhận được nhiều tiền nhất là: người thứ 4 -> người thứ 1 -> người thứ 2.
Với a = [5, 1, 3, 2], t = [3, 1, 2, 2] thì kết quả là orderConsignment(a, t) = 10.
Giải thích: mặc dù người thứ 2 chỉ có thể chờ được trong 1 phút nhưng người này lại có chi phí vận chuyển thấp nhất nên bưu cục sẽ không phục vụ người này. Thứ tự phục vụ để bưu cục nhận được nhiều tiền nhất là: người thứ 3 -> người thứ 4 -> người thứ 1.