SỬ DỤNG PHƯƠNG PHÁP QUY HOẠCH ĐỘNG GIẢI BÀI TOÁN BA LÔ 0-1 Bài toán xếp ba lô (Knapsack problem) toán tối ưu hóa tổ hợp (combinatorial optimization) Cho tập hợp phần tử, phần tử có trọng lượng giá trị khác nhau, xác định phần tử đưa vào tập hợp khác cho trọng lượng bé giới hạn cho trước, tổng giá trị phần tử lớn Tên toán bắt nguồn từ việc phải xếp đồ vật ba lô cho chứa nhiều đồ có giá trị Một cách phát biểu khác toán: Một tên trộm sau đột nhập vào nhà thấy có N loại đồ vật có kích thước giá trị khác Vật ta muốn mang đi, lại mang túi có dung lượng M (có thể chứa số đồ vật cho tổng kích thước nhỏ hay M) Vấn đề đặt cho tên trộm phải chọn lựa danh sách đồ vật mang cho tổng giá trị lấy cắp lớn Sơ lược Quy hoạch động (Dynamic programming) Ý tưởng để phát triển thuật toán quy hoạch động cho toán xếp ba lô: Bước 1: Cấu trúc: Tìm đặc điểm cấu trúc phương án tối ưu Phân rã vấn đề lớn thành nhiều vấn đề nhỏ Tìm liên kết cấu trúc phương án tối ưu giải pháp vấn đề nhỏ Bước 2: Nguyên tắc tối ưu: Định nghĩa giá trị phương án tối ưu phương pháp đệ quy Thể giải pháp vấn đề gốc giải pháp cho vấn đề nhỏ Bước 3: Tính từ lên (bottom-up computation): Tính toán giá trị giải pháp tối ưu cách tính toán từ lên cách sử dụng cấu trúc bảng Bước 4: Xây dựng giải pháp tối ưu: Tổng hợp giải pháp tối ưu thông tin tính toán từ vấn đề nhỏ Bước thường gộp chung lại Bài toán xếp ba lô dạng 0-1: Mỗi đồ vật có số lượng 1, tên trộm chọn lấy (1) không lấy (0) đồ vật Bài toán xếp ba lô 0-1 phát biểu dạng toán học sau: Giả sử có n phần tử từ x1 đến xn, xi có giá trị vi trọng lượng wi Trọng lượng tối đa ba lô W Và ngầm định giá trị trọng lượng đồ vật không âm Để đơn giản hóa ngầm định giá trị đồ liệt kê theo danh sách tăng dần trọng lượng Phân rã vấn đề lớn thành nhiều vấn đề nhỏ: Chúng ta xây dựng mảng V[0 n, w] Trong i <= ≤ n ≤ w ≤ W Giá trị cuối V[i,w] lưu trữ giá trị lớn (giá trị tổng hợp) tập hợp đồ vật {1, 2, ,i} có trọng lượng tối đa W Nếu tính toán tất giá trị mảng phần tử V[n, W] chứa giá trị lớn đồ mà bỏ vừa vào ba lô Định nghĩa giá trị giải pháp tối ưu cách đệ qui giải pháp cho vấn đề Thiết lập ban đầu: V[0, w] = với ≤ w ≤ W V[i, w] = - vô cho w ≤ 0, không hợp lệ Bước tính toán đệ qui: V[i,w] = Max(V[i−1,w],vi+V[i−1,w−wi]) (Giá trị ô V[i, w] Max giá trị ô đầu giá trị vi + giá trị chứa ba lô) Tính từ-dưới-lên (bottom-up computing) Đáy: V[0, w] = với tất ≤ w ≤ W Các dòng khác tính dòng một: V[i,w] = Max(V[i−1,w], vi+V[i−1,w−wi]) V[i,w] n 0 W bottom up Tuy nhiên bảng không mô tả tập hợp mang lại kết tối ưu Do phải sử dụng mảng Keep[i, w] để xác định tập hợp T phần tử mang lại giá trị lớn Nếu Keep[n, W] = phần tử n thuộc T Sau lặp lại trình với Keep[n−1,W−wn] (Tức phần tử thứ i=n−1 có wi=W−wn) Nếu Keep[n, W] = phần tử thứ n không thuộc T Và lặp lại trình xét cho Keep[n-1, W] Đánh giá độ phức tạp thuật toán Thuật toán giải toán túi có thời gian đánh giá O(nL) Thời gian phụ thuộc tuyến tính vào liệu vào L.Trên thực tế,thuật toán làm việc hiệu L không lớn Xem xét ví dụ cụ thể Giả sử có đồ (và đồ đặt biệt có v=0 w=0) lần lược có trọng lượng giá trị sau: Item1 có v1=5 w1=3 Item2 có v2=3 w2=2 Item3 có v3=4 w3=1 Và ba lô có W=5 Đầu tiên cần kẻ bảng (nói cách khác tạo array) sau: V[i,w] w=0 3 Keep 3 Chúng ta áp dụng qui hoạch động để điền giá trị vào bảng này, mục đích biết giá trị ô cuối V[3,5], ba đồ chọn để bỏ vào ba lô có dung lượng Một bảng V điền đầy đủ ta biết phải bỏ đồ vào ba lô hợp lý Nhưng không cho ta biết kết hợp đồ để đặt vào ba lô để có giá trị lớn nhất, mục đích bảng Keep Chi tiết: Đối với dòng thứ 2: Item1 có v1=5 w1=3 Dựa theo bảng V, dung lượng ba lô ba lô chứa Item ta điền vào ô Tuy nhiên dung lượng ba lô tăng lên Item nằm vừa ba lô Do điền (giá trị đồ vào bảng V) vào bảng Keep (cho biết đồ giữ ba lô, trống đơn vị) V[i,w] w=0 4 0 0 0 0 Keep 0 0 0 Tiếp theo, dung lượng ba lô 4, hiển nhiên đặt Item vào ba lô Ta so sánh giá trị đặt vào với giá trị V[0, 4] = 0, ta thấy > Cho nên ta loại bỏ giá trị trước Và trống đơn vị dung lượng, ta xem tiếp sử dụng Item trước (Item 0) bỏ vừa vào ba lô hay không? Giá trị V[0, 1] = câu trả lời Và bỏ vào ba lô hai Item Item với tổng giá trị + Tất nhiên ta điền vào Keep[1, 4] Tiếp tục với ô V[1, 5] ta có bảng sau: V[i,w] w=0 0 0 0 5 5 Keep 0 0 0 0 1 Đối với dòng thứ 3: Item1 có v1=5 w1=3 Item2 có v2=3 w2=2 Đối với dòng thứ 3, ta làm tương tự dòng thứ Tuy nhiên ô cuối dòng thứ V[2, 5] phức tạp chút chứa Item Item V[2, 1] = Vì Item vừa ba lô có dung lượng V[2, 2] = Vì có Item (v=3 w=2) vừa ba lô V[2, 3] = Vì phần tử hành (Item 2) bỏ vừa vào ba lô, có giá trị nhỏ bỏ phần tử V[1, 3] =5, nên chọn phần tử bỏ vào ba lô V[2, 4] = Lý V[2, 5] = Tương tự trên, ta chọn phần tử trước có giá trị cao phần tử hành, trống đơn vị, ta bỏ vào thêm V[2,2] = Tổng cộng có V[2, 5] = V[1, 5] + V[2,2] = Keep[2, 1] = Vì không chọn bỏ Item vào ba lô Keep[2, 2] = Vì chọn bỏ Item vào ba lô Keep[2, 3] = Vì phần tử hành Item không chọn, chọn phần tử V[1, 3] có giá trị cao bỏ vào ba lô Keep[2, 4] = Vì tương tự Keep[2, 5] = Vì có chọn bỏ Item vào ba lô, sau trống đơn vị ta bỏ thêm V[1, 3] = vào Do ta giữ phương án V[i,w] w=0 0 0 0 3 5 5 5 Keep 0 0 1 0 0 Đối với dòng thứ 4: Ta sử dụng Item có giá trị Item1 có v1 = w1 = Item2 có v2 = w2 = Item3 có v3 = w3 = V[3, 1] = Vì bỏ vừa Item (v=4, w=1) V[3, 2] = Vì bỏ vừa Item V[3, 3] = Vì bỏ vừa Item 3(v=4, w=1), trống đơn vị, bỏ thêm Item (v=3, w=2) Và lớn ô V[2, 3] = V[3, 4] = Vì bỏ vừa Item 3(v=4, w=1), trống đơn vị, bỏ thêm Item (v=5, w=3) Và lớn ô V[2, 4] = V[3, 5] = Tương tự Keep[3, 1] = Vì chọn bỏ Item vào ba lô Keep[3, 2] = Vì chọn bỏ Item vào ba lô Keep[3, 3] = Vì chọn bỏ Item vào ba lô Keep[3, 4] = Vì chọn bỏ Item vào ba lô Keep[3, 5] = Vì chọn bỏ Item vào ba lô Dựa vào giá trị cuối bảng V (V[4,3] = 9) Ta biết ba lô chứa tổng giá trị mà không vượt dung lượng ba lô V[i,w] w=0 0 0 0 5 5 5 Keep 0 0 1 1 1 1 0 0 Dựa vào mô tả ta tính toán tập hợp cấu thành phương án tối ưu cho toán Ta có n=3 W=5 Xét Keep[3,5] = ta ta đưa Item vào tập hợp T Tiếp theo xét: Keep[3−1,W−w3] = Keep[2,4] Keep[2, 4] = ta không đưa Item vào tập hợp T Sau xét tiếp Keep[n−1,W−w3]=Keep[1,4] = Do ta đưa Item vào tập hợp T Cuối ta thấy kết cuối toán xếp ba lô sau: Giá trị lớn lấy Vmax = T= {1,3} CODE CHƯƠNG TRÌNH

include

include int main(int argc, char* argv[]) { // khai bao bien int w; // Khoi luong cua balo int n; // So luong vat cho vao balo int KL[500]; // mang luu khoi luong cua cac vat; int GT[500]; // mang luu gia tri cua cac vat; int HamKetQua[500][500]; int i;// số chay theo số vat : từ >n int j;// số chạy theo trọng lượng balo : từ > w /* Phần nhập liệu đầu vào -*/ // Nhập khối lượng balo Giả thiết khối lượng balo nằm tới 500 // số 500 thay đổi tùy theo ta định nghĩa { printf("Nhap khoi luong ma balo co the duoc:= "); scanf("%d",&w); } while (w<3|| w>500); // Nhập số lượng đồ vật { printf("So vat dung de cho vao balo:= "); scanf("%d",&n); } while (n<3|| n>500); for (i=0;iPhần dùng để nhập mảng khối lượng đồ vật // Khối lượng đồ vật phải >=1 nhỏ khối lượng balo, thỏa mãn nhập lại { printf("KT Dovat[%d]:=", i+1 ); scanf("%d", &KL[i]); } while (KL[i]<1|| KL[i]>w); // Phần dùng để nhập mảng giá trị túi // Giá trị đồ vật phải >=1, nhỏ nhập lại { printf("GT Dovat[%d]:=", i+1 ); scanf("%d", >[i]); } while (GT[i]<1); } /* - Phần thuật toán xử lý chương trình -*/ // khởi tạo, balo không chứa đồ vật tất giá trị ban đầu for (j=0;j<=w; j++) { HamKetQua[0][j] =0; } // phần chương trình for(i=1;i<=n;i++) { for (j=0;j<=w;j++) { HamKetQua[i][j] = HamKetQua[i-1][j]; if (KL[i-1] <=j && HamKetQua[i][j] < HamKetQua[i-1][jKL[i-1]] + GT[i-1]) { HamKetQua[i][j] = HamKetQua[i-1][j-KL[i-1]] + GT[i-1]; } 10 } } /* Phần hiển thị kế hình -*/ // Hiển thị bảng phương án for(i=0; i<=n+1; i++) { // hien thị dòng tiều đề bảng phương án if (i==0) { printf(" GT "); printf(" KL "); printf("i|v"); for(j=0; j<=w; j++) { printf("%4d",j); } } // hiển thị dòng balo không chứa gói hàng else if (i==1) { printf(" "); printf(" "); printf("%4d",i-1); for(j=0; j<=w; j++) { printf("%4d",HamKetQua[i-1][j]); } } else // hiển thị nội dung bảng phương án { 11 printf("%4d",GT[i-2]); printf("%4d",KL[i-2]); printf("%4d",i-1); for(j=0; j<=w; j++) { printf("%4d",HamKetQua[i-1][j]); } } printf("\n"); } // Hiển thị đồ vật lựa chọn vào Ba lô j= w; printf("Cac Do vat duoc chon la:="); for (i= n;i>0;i ) { if (HamKetQua[i][j] != HamKetQua[i-1][j]) { j= j-KL[i-1]; printf("%4d",i); } } getch(); } 12 ... = 9) Ta biết ba lô chứa tổng giá trị mà không vượt dung lượng ba lô V[i,w] w =0 0 0 0 5 5 5 Keep 0 0 1 1 1 1 0 0 Dựa vào mô tả ta tính toán tập hợp cấu thành phương án tối ưu cho toán Ta có n=3... nằm vừa ba lô Do điền (giá trị đồ vào bảng V) vào bảng Keep (cho biết đồ giữ ba lô, trống đơn vị) V[i,w] w =0 4 0 0 0 0 Keep 0 0 0 Tiếp theo, dung lượng ba lô 4, hiển nhiên đặt Item vào ba lô Ta... trị V [0, 1] = câu trả lời Và bỏ vào ba lô hai Item Item với tổng giá trị + Tất nhiên ta điền vào Keep [1, 4] Tiếp tục với ô V [1, 5] ta có bảng sau: V[i,w] w =0 0 0 0 5 5 Keep 0 0 0 0 1 Đối với