TAILIEUCHUNG - bài giảng các chuyên đề phần 6

Nếu có chọn gói thứ i (tất nhiên chỉ xét tới trường hợp này khi mà Wi ≤ j) thì F[i, j] bằng giá trị gói thứ i là Vi cộng với giá trị lớn nhất có thể có được bằng cách chọn trong số các gói {1, 2, ., i - 1} với giới hạn trọng lượng j - Wi. Tức là về mặt giá trị thu được: F[i, j] = Vi + F[i - 1, j - Wi] Vì theo cách xây dựng F[i, j] là giá trị lớn nhất có thể, nên F[i, j] sẽ là max. | Quy hoạch động 12 Nếu có chọn gói thứ i tất nhiên chỉ xét tới trường hợp này khi mà Wi j thì F i j bằng giá trị gói thứ i là Vi cộng với giá trị lớn nhất có thể có được bằng cách chọn trong số các gói 1 2 . i - 1 với giới hạn trọng lượng j - Wi. Tức là về mặt giá trị thu được F i j Vi F i - 1 j - Wi Vì theo cách xây dựng F i j là giá trị lớn nhất có thể nên F i j sẽ là max trong 2 giá trị thu được ở trên. 2. Cơ sở quy hoạch động Dễ thấy F 0 j giá trị lớn nhất có thể bằng cách chọn trong số 0 gói 0. 3. Tính bảng phương án Bảng phương án F gồm n 1 dòng M 1 cột trước tiên được điền cơ sở quy hoạch động Dòng 0 gồm toàn số 0. Sử dụng công thức truy hồi dùng dòng 0 tính dòng 1 dùng dòng 1 tính dòng 2 . đến khi tính hết dòng n. 01 M 0 1 2 0 0 0 0 n 4. Truy vết Tính xong bảng phương án thì ta quan tâm đến F n M đó chính là giá trị lớn nhất thu được khi chọn trong cả n gói với giới hạn trọng lượng M. Nếu F n M F n - 1 M thì tức là không chọn gói thứ n ta truy tiếp F n - 1 M . Còn nếu F n M F n - 1 M thì ta thông báo rằng phép chọn tối ưu có chọn gói thứ n và truy tiếp F n - 1 M - Wn . Cứ tiếp tục cho tới khi truy lên tới hàng 0 của bảng phương án. Bài toán cái túi program The_Bag const max 100 var W V Array of Integer F array of Integer n M Integer procedure Enter Nhập dữ liệu từ thiết bị nhập chuẩn Input var i Integer begin ReadLn n M for i 1 to n do ReadLn W i V i end procedure Optimize Tính bảng phương án bằng công thức truy hồi var i j Integer begin FillChar F 0 SizeOf F 0 0 Điền cơ sở quy hoạch động for i 1 to n do for j 0 to M do begin Tính F i j Lê Minh Hoàng Quy hoạch động 13 F i j F i - 1 j Giả sử không chọn gói thứ i thì F i j F i - 1 j Sau đó đánh giá nếu chọn gói thứ i sẽ được lợi hơn thì đặt lại F i j if j W i and F i j F i - 1 j - W i V i then F i j F i - 1 j - W i V i end end procedure Trace Truy vết tìm nghiệm tối ưu begin WriteLn F n M In ra giá trị lớn nhất có thể kiếm được while n 0 do Truy vết trên bảng phương án từ hàng

• Cơ sở dữ liệu
• thuật toán tìm kiếm
• các chuyên đề thuật toán
• lập trình pascal
• lập trình các giải thuật
• Các thuật toán tìm kiếm
• Tìm kiếm trên đồ thị
• Bài toán tìm kiếm trên đồ thị
• Thuật toán tìm kiếm theo chiều rộng
• Thuật toán tìm kiếm theo chiều sâu
• Tìm kiếm tuần tự
• Tìm kiếm nhị phân
• Tìm kiếm dựa trên quy hoạch động
• Tìm kiếm dựa trên đệ quy
• Tìm kiếm dựa trên phân vùng
• Khái niệm tìm kiếm
• Bài toán tìm kiếm
• Tìm kiếm trên dãy chưa sắp
• Cấu trúc dữ liệu
• Kỹ thuật tìm kiếm
• Tìm kiếm trên mảng
• Giải thuật tìm kiếm
• Tìm kiếm trên tập tin
• Tìm kiến tuyến tính
• Thuật toán tìm kiếm tối ưu
• Tìm kiếm cứu nạn
• Thuật toán vi khuẩn
• Tính toán phương án tìm kiếm tối ưu
• Tàu tìm kiếm cứu nạn
• Lý thuyết đồ thị
• Bài giảng Lý thuyết đồ thị
• Thuật toán tìm kiếm trên đồ thị
• Ứng dụng thuật toán tìm kiếm đồ thị
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu và giải thuật
• Khái niệm về tìm kiếm
• Phương pháp tìm kiếm tuần tự
• Phương pháp tìm kiếm nhị phân
• Thuật toán tìm kiếm nhị phân
• Thuật toán tìm kiếm nhị phân cơ bản
• Thuật toán Quicksort
• Cách tìm kiếm nhị phân
• chiến lược tìm kiếm mù
• Tìm kiếm beam
• Tìm kiếm leo đồi
• tìm kiếm tối ưu
• Tìm kiếm có đối thủ
• Tìm kiếm mô phỏng sự tiến hóa
• Thuật toán di truyền
• Bài toán giải thuật
• Chiến lược tìm kiếm
• Tìm kiếm trình tự
• Lập trình C
• Bài giảng Lập trình căn bản
• Bài toán sắp xếp
• Thuật toán tìm kiếm tuần tự
• Thuật toán sắp xếp nổi bọt
• khoa học
• tự nhiên
• toán học
• Các thuật toán tìm kiếm trên đồ thị
• Các giải thuật tìm kiếm
• Giải thuật tìm kiếm tuyến tính
• Giải thuật Tìm kiếm nhị phân
• Các giải thuật sắp xếp
• Tóm tắt Luận án Thạc sĩ
• Hệ thống thông tin
• Tìm kiếm chuỗi DNA
• Tìm kiếm tương tự nhanh
• Bài giảng Toán rời rạc 2
• Toán rời rạc 2
• Toán rời rạc
• Ứng dụng của thuật toán tìm kiếm
• Bài giảng Tìm kiếm heuristic leo đồi
• Thuật giải di truyền
• Thuật giải leo đồi
• Các thuật toán tìm kiếm cục bộ
• Lựa chọn của thuật giải di truyền
• Nội dung về thuật giải leo đồi
• Bài giảng Cấu trúc dữ liệu
• Tìm kiếm trên danh sách
• Tìm kiếm trên văn bản
• Bài giảng Tìm kiếm
• Kỹ thuật lập trình
• Bài giảng Các hệ thống thông minh nhân tạo
• Hệ thống thông minh nhân tạo
• Bài toán tìm kiếm 1
• Cây tìm kiếm
• Thuật toán tìm kiếm mù
• Bài toán tìm đường đi
• Thuật giải HEURISTIC
• phương pháp tìm kiếm HEURISTIC
• thuật toán tìm kiếm leo đồi
• tìm kiếm ưu tiên tối ưu
• ứng dụng giải bài toán ta canh
• chiến lược tìm kiếm lai
• Bài giảng Thuật toán Ứng dụng
• Thuật toán Ứng dụng
• Cấu trúc dữ liệu trừu tượng
• Cài đặt tìm kiếm ở thư viện
• tài liệu học đại học
• bài giảng quy hoạch tuyến tính
• Khoa học máy tính
• tìm kiếm tuyến tính
• Tìm kiếm theo chiều sâu
• Tìm kiếm theo chiều rộng
• Ứng dụng các thuật toán
• Bài giảng Tìm kiếm đối kháng
• Tìm kiếm đối kháng
• Tìm kiếm đối kháng trò chơi
• Thuật toán MINIMAX
• Hàm lượng giá
• Tìm kiếm cắt nhánh