TAILIEUCHUNG - Algorithms Programming - Thuật Toán Số phần 6

Quy hoạch động {Hàm Find, tìm vị trí j mà nếu đem ai ghép vào đầu dãy con đơn điệu tăng dài nhất bắt đầu từ aj sẽ được dãy đơn điệu tăng dài nhất bắt đầu tại ai} function Find(i: Integer): Integer; var inf, sup, median. | Quy hoạch động 147 Hàm Find tìm vị trí j mà nếu đem Ui ghép vào đầu dãy con đơn điệu tăng dài nhất bắt đầu từ aj sẽ được dãy đơn điệu tăng dài nhất bắt đầu tại ai function Find i Integer Integer var inf sup median j Integer begin inf 1 sup m 1 repeat Thuật toán tìm kiếm nhị phân median inf sup div 2 j StartOf median if a j a i then inf median Luôn để aStartof inf Ui k astartof sup else sup median until inf 1 sup Find StartOf inf end procedure Optimize var i j k Integer begin for i n downto 0 do begin j Find i k L j 1 if k m then begin m k StartOf k i end else if a StartOf k a i then StartOf k i L i k T i j end end procedure Result var f Text i Integer begin Assign f OutputFile Rewrite f WriteLn f m - 2 i T 0 while i n 1 do begin WriteLn f a i a i i T i end Close f end begin Enter Init Optimize Result end. Dễ thấy chi phí thời gian thực hiện giải thuật này cấp O nlogn đây là một ví dụ điển hình cho thấy rằng một công thức truy hồi có thể có nhiều phương pháp tính. Lê Minh Hoàng 148 Chuyên đề . BÀI TOÁN CÁI TÚI Trong siêu thị có n gói hàng n 100 gói hàng thứ i có trọng lượng là Wi 100 và trị giá Vi 100. Một tên trộm đột nhập vào siêu thị tên trộm mang theo một cái túi có thể mang được tối đa trọng lượng M M 100 . Hỏi tên trộm sẽ lấy đi những gói hàng nào để được tổng giá trị lớn nhất. Input file văn bản Dòng 1 Chứa hai số n M cách nhau ít nhất một dấu cách n dòng tiếp theo dòng thứ i chứa hai số nguyên dương Wi Vi cách nhau ít nhất một dấu cách Output file văn bản Dòng 1 Ghi giá trị lớn nhất tên trộm có thể lấy Dòng 2 Ghi chỉ số những gói bị lấy 5 11 11 3 3 5 2 1 4 4 5 4 9 10 4 4 Cách giải Nếu gọi F i j là giá trị lớn nhất có thể có bằng cách chọn trong các gói 1 2 . i với giới hạn trọng lượng j. Thì giá trị lớn nhất khi được chọn trong số n gói với giới hạn trọng lượng M chính là F n M . . Công thức truy hồi tính F i j . Với giới hạn trọng lượng j việc chọn tối ưu trong số các gói 1 2 . . i - 1 i để có giá trị lớn nhất sẽ có .

• Kỹ thuật lập trình
• Tài liệu IT
• Tài liệu lập trình
• Thuật toán
• Toán logic
• Giải thuật
• Hàm số
• thủ thuật lập trình
• tài chính
• ngân hàng
• kế toán
• quản lý tài chính
• tài liệu tài chính
• tài liệu về ngân hàng
• Tài liệu kinh doanh
• hướng dẫn hạch toán
• Hạch toán doanh nghiệp
• Tài sản doanh nghiệp