Caheo2010
10-01-2008, 22:41
Bài toán như sau:Cho n công việc (n nguyên dương bé hơn 500)được đánh số từ 1 đến n,công việc i cần làm trong t(i) giờ liên tục.Công việc i nếu làm xong không muộn hơn giờ thứ d(i)(d(i) bé hơn 1000) sẽ thu được lợi nhuận
g(i)(g(i) bé hơn 2000).Tại mỗi thời điểm không được làm nhiều hơn 1 công việc và có thể bắt đầu thực hiện các công việc từ thời điểm 0,thời điểm i-1 xem như bắt đầu giờ thứ i.Hãy chọn các công việc để thực hiện sao cho tổng lợi nhuận thu được là lớn nhất!
Yêu cầu cụ thể về input/output như sau:
Dữ liệu vào được cho file văn bản jobs.in trong đó dòng đầu tiên là số n,tiếp theo là n,dòng, dòng thứ i trong số n dòng này là:t(i),d(i),g(i) .
Kết quả được ghi ra files văn bản jobs.out trong đó dòng thứ nhất ghi tổng lợi nhuận thu được, dòng thứ hai ghi số m là số công việc được chọn để thực hiện,tiếp theo là m dòng. mỡi dòng ghi hai số x,y với ý nghĩa việc x làm giờ thứ y.
Bài này mình bị bí .Mong bác nào biết thì chỉ giáo tận tình nhé ,nếu có thể bầng ngông ngữ C /C++ nhé.Còn mấy hôm nữa là thi rồi...Thku!
g(i)(g(i) bé hơn 2000).Tại mỗi thời điểm không được làm nhiều hơn 1 công việc và có thể bắt đầu thực hiện các công việc từ thời điểm 0,thời điểm i-1 xem như bắt đầu giờ thứ i.Hãy chọn các công việc để thực hiện sao cho tổng lợi nhuận thu được là lớn nhất!
Yêu cầu cụ thể về input/output như sau:
Dữ liệu vào được cho file văn bản jobs.in trong đó dòng đầu tiên là số n,tiếp theo là n,dòng, dòng thứ i trong số n dòng này là:t(i),d(i),g(i) .
Kết quả được ghi ra files văn bản jobs.out trong đó dòng thứ nhất ghi tổng lợi nhuận thu được, dòng thứ hai ghi số m là số công việc được chọn để thực hiện,tiếp theo là m dòng. mỡi dòng ghi hai số x,y với ý nghĩa việc x làm giờ thứ y.
Bài này mình bị bí .Mong bác nào biết thì chỉ giáo tận tình nhé ,nếu có thể bầng ngông ngữ C /C++ nhé.Còn mấy hôm nữa là thi rồi...Thku!