Dễ dàng tính được độ phức tạp của giải thuật vẫn là O(n2). Bài toán cái ba lô Sử dụng kĩ thuật quy hoạch động để giải bài toán cái ba lô đã trình bày trong mục với một lưu ý là các số liệu đều cho dưới dạng số nguyên. Giả sử X[k,V] là số lượng đồ vật k được chọn, F[k,V] là tổng giá trị của k đồ vật đã được chọn và V là trọng lượng còn lại của ba lô, k = 1n, V = 1W. . | Giải thuật Kĩ thuật thiết kế giải thuật 2 V 1 1 3 FOR i 2 TO n DO BEGIN 4 p1 V 0 5 FOR j 1 TO i-1 DO BEGIN 6 p2 V j 7 V j p1 p2 8 P1 p2 END 9 V i 1 END 10 Comb V k END Dễ dàng tính được độ phức tạp của giải thuật vẫn là O n2 . Bài toán cái ba lô Sử dụng kĩ thuật quy hoạch động để giải bài toán cái ba lô đã trình bày trong mục với một lưu ý là các số liệu đều cho dưới dạng số nguyên. Giả sử X k V là số lượng đồ vật k được chọn F k V là tổng giá trị của k đồ vật đã được chọn và V là trọng lượng còn lại của ba lô k V . Trong trường hợp đơn giản nhất khi chỉ có một đồ vật ta tính được X 1 V và F 1 V với mọi V từ 1 đến W như sau X 1 V V DIV g1 và F 1 V X 1 V v1. Giả sử ta đã tính được F k-1 V khi có thêm đồ vật thứ k ta sẽ tính được F k V với mọi V từ 1 đến W. Cách tính như sau Nếu ta chọn xk đồ vật loại k thì trọng lượng còn lại của ba lô dành cho k-1 đồ vật từ 1 đến k-1 là U V-xk gk và tổng giá trị của k loại đồ vật đã được chọn F k V F k-1 U xk vk với xk thay đổi từ 0 đến yk V DIV gk và ta sẽ chọn xk sao cho F k V lớn nhất. Ta có công thức truy hồi như sau X 1 V V DIV g1 và F 1 V X 1 V v1. F k V Max F k-1 V-xk gk xk vk với xk chạy từ 0 đến V DIV gk. Sau khi xác định được F k V thì X k V là xk ứng với giá trị F k V được chọn trong công thức trên. Để lưu các giá trị trung gian trong quá trình tính F k V theo công thức truy hồi trên ta sử dụng một bảng gồm n dòng từ 1 đến n dòng thứ k ứng với đồ vật loại k và W 1 cột từ 0 đến W cột thứ V ứng với trọng lượng V. Mỗi cột V bao gồm hai cột nhỏ cột bên trái lưu F k V cột bên phải lưu X k V . Trong lập trình ta sẽ tổ chức hai bảng tách rời là F và X. Ví dụ bài toán cái ba lô với trọng lượng W 9 và 5 loại đồ vật được cho trong bảng sau Đồ vật Trọng lượng gi Giá trị vi Nguyễn Văn Linh Trang 59 Giải thuật Kĩ thuật thiết kế giải thuật 1 3 4 2 4 5 3 5 6 4 2 3 5 1 1 Ta có bảng F k V và X k V như sau trong đó mỗi cột V có hai cột con cột bên trái ghi F k V và cột bên phải ghi X k V . XV k 0 1 2 3 4 5 6 7 8 9 1 0 0
