Bài Tập Môn Toán Rời Rạc
Đề Bài:
Thuật
Toán Cái Túi
Người thực hiện: Ngô Xuân Cường MSV: 1466704
Nguyễn
Văn Bẩy MSV:1401295
Nguyễn
Sỹ Giang MSV:1400207
Giảng Viên:
Trần Xuân Thanh
Mục Lục
Giới thiệu:
Chương I: Bài toán
cái túi
1.1 Giới thiệu
1.2
Bài
toán cái túi dạng 0-1
1.3
Bài
toán cái túi dạng phân số
Chương II
Chương III Giải bài toán cái túi bằng thuật
toán tham lam(Greedy)
3.1 Giải bài toán này bằng thuật toán tham
lam
Chương IV: Giải bài toán cái túi bằng thuật
toán nhánh cận
4.1 Giới thiệu
4.2 Ứng dụng
Giới
thiệu :
Báo cáo này sẽ trình bày về thuật toán
giải quyết bài toán cái túi
Chương I : Bài toán cái túi
1.1 GIỚI THIỆU.
Bài toán cái túi (hay còn gọi là bài toán xếp ba lô) là một bài toán tối ưu
tổ hợp. Bài toán được đặt tên từ vấn đề chọn những gì quan trong có thể nhét vừa
vào một cái túi (với giới hạn khối lượng) để mang theo trong một chuyến đi.
Ví dụ về bài toán cái túi trong giới hạn một chiều: chọn
các hộp nào để làm cho giá trị tiền là cực trại khi tổng trọng lượng không vượt
quá 15kg? Bài toán đa chiều có thể xét đến khối lượng riêng và kích thước của hộp,
đó là bài toán xếp vali điển hình(packing problem)
Ta có n loại đồ vật, từ 1 tới n. Mỗi đồ vật thứ i có trọng
lượng w[i] và giá trị v[i]. Trọng lượng tối đa mà túi có thể mang được là S.
1.2 BÀI TOÁN
CÁI TÚI DẠNG 0-1.
Hạn chế số đồ vật thuộc mỗi loại là 0 (không được chọn )
và 1 (được chọn).
Bài toán cái túi bị chặn hạn chế số đồ vật huộc mỗi loại nào đó không được vượt quá
một lượng nào đó.
Bài cái túi không bị
chặn không có một hạn chế nào về số lượng đồ vật mỗi loại.
Một trường hợp đặc biệt của bài toán này nhận được nhiều
quan tâm, đó là bài toán với các tính chất:
· là
một bài toán quyết định
· là
một bài toán 0/1
· với
mỗi đồ vật, chi phí bằng giá trị: C = V
Trường hợp đặc biệt này được gọi là
bài toán tổng các tập con (subset sum problem). Với một số lý do, trong ngành mật
mã học, người ta thường dùng cụm từ "bài toán cái túi khi thực ra đang có
ý nói về "bài toán tổng con".
Bài toán cái túi thường được giải bằng
quy hoạch động, tuy chưa có một thuật toán thời gian đa thức cho bài toán tổng
quát. Cả bài cái túitổng quát và bài toán tổng con đều là các bài NP-khó, và điều
này dẫn đến các cố gắng sử dụng tổng con làm cơ sở cho các hệ thống mật mã hóa
khóa công khai, chẳng hạn Merkle-Hellman. Các cố gắng này thường dùng nhóm thay
vì các số nguyên. Merkle-Hellman và một số thuật toán tương tự khác đã bị phá,
do các bài toán tổng con cụ thể mà họ tạo ra thực ra lại giải được bằng các thuật
toán thời gian đa thức.
Phiên bản bài toán quyết định của bài
toán cái túi được mô tả ở trên là NP-đầy đủ và trong thực tế là một trong 21
bài toán NP-đầy đủ của Karp.
1.3 BÀI TOÁN
CÁI TÚI DẠNG PHÂN SỐ
Với mỗi loại, có thể chọn một phần của
nó (ví dụ: 1Kg bơ có thể được cắt ra thành nhiều phần để bỏ vào ba lô)
Chương 2: Giải bài toán cái túi bằng
thuật toán trực tiếp (Brute-force)
Phương pháp này duyệt tất cả khả
năng chất đồ vào túi, tìm cách chất có tổng giá trị lớn nhất trong số các cách
chất co tổng trọng lượng các đồ vật không quá dung lượng của túi
Chương 3: Giải bài toán cái túi bằng
thuật toán tham lam
3.1 Thực hiện bài toán này bằng thuật
toán tham lam
Các hàm được sử dụng :
· swap
(x,y) được dùng để đổi chỗ
biến x và y khi sắp xếp
· nhap()
dùng để nhập dữ liệu từ bàn phím
· sapxep()
được dùng để sắp xếp lại mảng theo thứ tự giảm dần của tỉ lệ v[i]/w[i] , tức là
tỉ lệ giảm dần của giá trị trên khối lượng mỗi đồ vật
· thamlam()
lần lượt trọn các đồ vật đã được sắp xếp theo thứ tự giảm dần của giá trị trên
khối lượng, biến kỉ lục ghi nhận kết quả tốt nhất khi thực hiện
Độ phức tạp:
· Nếu
sử dụng sắp xếp đơn giản (chèn, nổi bọt…) thì độ phức tạp của cả bài toán là
O(n2)
· Nếu
sử dụng quick sort hoặc merge sort thì độ phức tạp là O(nlogn) tốt hơn so với
giải trực tiếp
· giảm
dần của giá trị trên khối lượng mỗi đồ vật
· thamlam()
lần lượt trọn các đồ vật đã được sắp xếp theo thứ tự giảm dần của giá trị trên
khối lượng, biến kỉ lục ghi nhận kết quả tốt nhất khi thực hiện
Độ phức tạp:
· Nếu
sử dụng sắp xếp đơn giản (chèn, nổi bọt…) thì độ phức tạp của cả bài toán là
O(n2)
· Nếu
sử dụng quick sort hoặc merge sort thì độ phức tạp là O(nlogn) tốt hơn so với
giải trực tiếp
Chương IV: Giải bài toán cái túi bằng thuật toán nhánh
cận
4.1 Giới thiệu.
Một bài toán tìm phương án tối ưu đơn thuần chỉ cần liệt kê
tập tất cả các phương
án và chọn phương án tốt nhất. Tuy nhiên như thế ta phải tốn
kém nhiều thời gian cho
quá trình giải bài toán. Thử nghĩ nếu trong quá trình tìm kết
quả cho một phương án,
nhận thấy phương án này không thể là phương án tối ưu được
liệu ta có nên bỏ qua để
duyệt phương án khác hay không ?
Kỹ thuật nhánh cận là như vậy. Trong quá trình tìm lời giải
của một phương án,
luôn xây dựng điều kiện nếu đi theo thương án này liệu có tốt
hơn các phương án đã có
hay không nhằm mục đích loại bỏ sớm các phương án không dẫn
đến lời giải tối ưu.
Cụ thể luôn xây dựng một giá trị lớn nhất (cận) đạt được nếu
đi theo phương án
(nhánh) này từ đó sẽ quyết định đi theo nhánh có cận cho là
tốt nhất. Vì thế nên nó mới
có tên là kỹ thuật nhánh cận ( Branch and Bound ).
4.2 Ứng dụng.
Ví Dụ: Có một tên trộm
mang theo một cái túi có thể đựng trọng lượng tối đa là M
vào một cửa hàng có n loại đồ vật, mỗi loại đồ vật có một
giá trị (v) và trọng lượng (w)
riêng ( giả sử số lượng mỗi đồ vật là rất nhiều ). Hỏi tên
trộm chọn những loại đồ vật
nào với số lượng bao nhiêu để tổng trọng lượng không vượt
quá trọng lượng tối đa của
cái túi (M) và tổng giá trị của các đồ vật (V) là lớn nhất ?
Áp dụng kỹ thuật nhánh cận để giải bài toán.
Ký hiệu : w[i] là trọng lượng của loại đồ vật i. (i = 1..n).
v[i] là giá trị của loại đồ vật i. (i = 1..n).
Mô hình bài toán có thể đưa về dạng bài toán quy hoạch tuyến
tính nguyên tìm
vectơ x = [ x1 , .. , xn ] ( với x1, .. , , xn là số lượng
loại đồ vật 1,..,n được chọn ) như sau.
Hàm mục tiêu : f = v1*x1 + ... + vn*xn max.
Hệ ràng buộc :
w1*x1 + .. + wn*xn ≤ M
xi ≥ 0 ( i = 1 .. n )
Để đánh giá giá trị của đồ vật so với trọng lượng ta dùng hệ
số giá trị :
vi/wi ( i = 1..n).
Ưu tiên các đồ vật có hệ số giá trị lớn chọn trước nên ta sắp
xếp các loại đồ vật
từ cao đến thấp theo hệ số giá trị.
v1/w1 ≥ v2/w2 ≥ .. ≥ vn/wn.
Dễ thấy giá trị tối đa của cái túi f(x) ≤ M*v1/w1.
Vậy x1 có thể nhận các giá trị trong tập S1 = { k1 | k1 ≤
M/w1 }.
Ứng với mỗi giá trị x1 = k1 S ta thiết lập một nhánh
phương án có cập trên là:
k1*v1 + ( M – k1*w1 )* v2/w2.
Và trong nhánh này, x2 có thể nhận các giá trị trong tập:
S2 = { k2 | k2*w2 ≤ ( M – k1*w1 ) }
Ứng với mỗi giá trị x2 = k2 S2 ta lại thiết lập một nhánh
phương án có cận trên
là : k1*v1 + k2*v2 + ( M – k1*w1 - k2*w2)* v3/w3.
Tương tự quá trình thiết lập nhánh và cận trên cứ lặp lại
cho tới khi nào không
thể chọn thêm một đồ vật nào nữa. (túi không thể chứa thêm đồ
vật nào nữa).
Để tìm phương án tối ưu ta đi theo nhánh có cận lớn nhất.
Ký hiệu : a : giá trị đồ vật đang đạt được, b: cận trên của
nhánh, M’ là trọng
lượng còn lại.
Chương trình (C):
Input : File balo.inp ( Đã xếp theo thứ tự nhỏ dần của
v[i]/w[i].
4 8
5 3 2 4
10 5 3 6
Giải thích: File balo.inp tương ứng với:
n M
w[1] w[2] w[3] w[4]
v[1] v[2] v[3] v[4]
Ouput: File balo.out
15
1 1 0 0
Giải thích: File balo.out tương ứng với:
Vmax //Giá trị tối ưu.
x[1] x[2] x[3] x[4] //Số lượng loại đồ vật được chọn.
Code:
#include<iostream>
#include<stdio.h>
#include<conio.h>
#define MAX 100
int x[MAX],y[MAX];
int w[MAX];
int v[MAX];
int n;
int m;
int wrem;
int a;
float b;
int vmax,vsel,wsel;
FILE *fp;
char *finp = "balo.inp";
char *fout = "balo.out";
void init();
void ouput();
void ghinhan();
void Try(int i);
void main(){
init();
Try(1);
output();
getch();
}
void init(){
int i;
if((fp=fopen(finp,"r"))!=NULL){
fscanf(fp,"%d %d\n",&n,&m);
for(i=1;i<=n;i++){
fscanf(fp,"%d",&w[i]);
}
fscanf(fp,"\n");
for(i=1;i<=n;i++){
fscanf(fp,"%d",&v[i]);
}
//======
a=0;
wrem=m;
b=wrem*v[1]/(float)w[1];
vmax = 0;
vsel=0;
wsel=0;
fclose(fp);
}
else{
printf("Khong tim thay file input");
exit(1);
}
}
void output(){
if((fp=fopen(fout,"w"))!=NULL){
int i;
fprintf(fp,"%d\n",vmax);
for(i=1;i<=n;i++){
fprintf(fp,"%3d",y[i]);
}
fclose(fp);
}
else{
printf("Khong tim thay file output");
}
}
void ghiNhan(){
int i;
if(vmax<vsel){
vmax=vsel;
for(i=1;i<=n;i++){
y[i]=x[i];
}
}
}
void Try(int i){
int j;
for(j=0;j<=wrem/(float)w[i];j++){
b=vsel+j*v[i] + (wrem-j*w[i])*v[i+1]/(float)w[i+1];
if(b>=vmax){
x[i]=j;
vsel = vsel + j*v[i];
wsel = wsel + j*w[i];
wrem = wrem - j*w[i];
if((i==n)||(wrem<=0))
else
ghiNhan();
Try(i+1);
x[i] = 0;
vsel = vsel - j*v[i];
wsel = wsel - j*w[i];
wrem = wrem + j*w[i];
}
}
Return 0;
}
Không có nhận xét nào:
Đăng nhận xét