Giới thiệu về thuật toán tham lam - Greedy Algorithm(Phần 2)

Ví dụ về thuật toán tham lam_ BÀI TOÁN BALO Yêu cầu Cho một cái ba lô có thể đựng một trọng lượng W và n loại đồ vật, đồ vật thứ i có trọng ...

Ví dụ về thuật toán tham lam_ BÀI TOÁN BALO

Yêu cầu


Cho một cái ba lô có thể đựng một trọng lượng W và n loại đồ vật, đồ vật thứ i có trọng lượng gi và giá trị vi. Tất cả các loại đồ vật đều có số lượng không hạn chế. Tìm một cách lựa chọn các đồ vật đựng vào ba lô (chọn các loại đồ vật nào, mỗi loại lấy bao nhiêu) sao cho tổng trọng lượng không vượt quá W và tổng giá trị là lớn nhất.

Theo yêu cầu của bài toán thì ta cần những đồ vật có giá trị cao mà trọng lượng lại nhỏ để sao cho có thể mang được nhiều “đồ quý”, sẽ là hợp lý khi ta quan tâm đến yếu tố “đơn giá” của từng loại đồ vật tức là tỷ lệ giá trị/trọng lượngĐơn giá càng cao thì đồ càng quý.

Từ đó ta có kỹ thuật Tham lam áp dụng cho bài toán này là:
1. Tính đơn giá cho các loại đồ vật.
2. Xét các loại đồ vật theo thứ tự đơn giá từ lớn đến nhỏ.
3. Với mỗi đồ vật được xét sẽ lấy một số lượng tối đa mà trọng lượng còn lại của ba lô cho phép.
4. Xác định trọng lượng còn lại của ba lô và quay lại bước 3 cho đến khi không còn có thể chọn được đồ vật nào nữa.



Ví dụ

Ta có một ba lô có trọng lượng là 37 và 4 loại đồ vật với trọng lượng và giá trị tương ứng được cho trong bảng (hình 1)

Click image for larger version  Name: Untitled1.png Views: 1 Size: 4,2 KB ID: 60463


Từ bảng đã cho ta tính đơn giá cho các loại đồ vật và sắp xếp các loại đồ vật này theo thứ tự đơn giá giảm dần ta có bảng (hình 2).

Click image for larger version  Name: Untitled2.png Views: 1 Size: 4,8 KB ID: 60464

Theo đó thì thứ tự ưu tiên để chọn đồ vật là B, A, D và cuối cùng là C.

Vật B được xét đầu tiên và ta chọn tối đa 3 cái vì mỗi cái vì trọng lượng mỗi cái là 10 và ba lô có trọng lượng 37. Sau khi đã chọn 3 vât loại B, trọng lượng còn lại trong ba lô là 37 - 3*10 = 7. Ta xét đến vật A, vì A có trọng lượng 15 mà trọng lượng còn lại của balô chỉ còn 7 nên không thể chọn vật A. Xét vật D và ta thấy có thể chọn 1 vật D, khi đó trọng lượng còn lại của ba lô là 7-4 = 3. Cuối cùng ta chọn được một vật C.Như vậy chúng ta đã chọn 3 cái loại B, một cái loại D và một cái loại C. Tổng trọng lượng là 3*10 + 1*4 + 1*2 = 36 và tổng giá trị là 3*25+1*6+1*2 = 83.

Thuật toán

Hàm sắp xếp.
Bước 1: Đặt i=0.
Bước 2: Nếu i <= n-1, Bước 3, ngược lại Bước 9
Bước 3: Đặt j=0.
Bước 4: Nếu j <= n, Bước 5, ngược lại Bước 8
Bước 5: Nếu t[i].Dongia<t[j].Dongia, Bước 6, ngược lại Bước 7
Bước 6: Đặt i = bientam.
i=j.
j=bientam.
Bước 7: Đặt j=j+1, quay lại Bước 4.
Bước 8: Đặt i=i+1,quay lại Bước 2.
Bước 9: Kết thúc.

Sơ đồ khối.

Click image for larger version  Name: Untitled3.png Views: 1 Size: 21,6 KB ID: 60465


Hàm Thuật toán.
Bước 1: Đặt i = 0, S=W
Bước 2: Nếu i < n, Bước 3,ngược lại Bước 8
Bước 3: Đặt t[i].Phuongan = S / t[i].Trongluong.
Bước 4: Đặt S = S - (t[i].Phuongan * t[i].Trongluong).
Bước 5: Kết xuất “Phuongan”
Bước 6: Đặt i = i + 1, quay lại Bước 3.
Bước 7: Kết xuất “ Trong luong con du cua balo”
Bước 7: Kết thúc.
Sơ đồ khối

Click image for larger version  Name: Untitled4.png Views: 1 Size: 15,5 KB ID: 60466

Đây là 2 hàm chính mình sử dụng trong đoạn code. Code mình viết bằng C++

Note :
Xin lỗi về sự chậm trễ 
Nếu ai cần code có thể comment mail bên dưới mình sẽ gửi. Vì do đoạn code khá dài và có vài kí tự không viết được trên trang này nên mình không thể đăng đoạn code được . Thanks

COMMENTS

Tên

.:: Connect Trojan ::.,111,.htaccess,2,0-day,3,2017,2,Add-on,16,Affiliate,1,Anotador,1,AutoIT,17,BackDoor,1,Bán Sách,13,banhangonline,1,Bảo Mật,169,Bất Động Sản Tại Tiền Giang,5,Bestsellers,13,Binder,1,blog,31,Blogger,4,Blogger Template,1,Botnet,3,Brute,1,Bug Bounty,1,Bypass,10,camera,1,ceh,1,Châu Tinh Trì,2,Checked,6,Chrome,21,Code,5,coin hive,1,Coin-Hive,2,CoinHive,1,Connect Trojan,342,Connect Trojan ::.,1,Cổ Tích,2,Crack,3,Crypto,5,CSRF,5,CSS,2,Cuộc Sống,1,Dau tu,8,DDoS,6,Designer,1,Dich vụ,1,DNS,4,Download,2,du-an,3,DVD LUMION Tiếng Việt của anh Dũng Già Pro,1,Đam Mỹ,1,điện,1,Đồ Họa,215,Đô Thị,16,e11.me,1,ebook,16,ebook free,295,eBook Phệ Hồn Nghịch Thiên,1,eBook Thịnh Thế Địch Phi,1,Encrypt,1,Encryption,1,epub,76,epub [Tiên hiệp],1,ET-Logger,1,exploit,23,Exploitation,1,Extractor,2,facebook,69,FireFox,15,Flood,2,Forensic,7,full prc,2,game,177,Gerador,3,Gerenciador,1,Get Root,3,GHDB,3,Giả Tưởng,1,giaitri,1,Google,15,H&Y Shop,2,Hacker,3,Hacking,16,Hacking and Security,6,Hacking Tools,36,Hành Động,3,He Thong Site Phim,25,Hijacking,6,Hình Sự,1,hivecoin.hive coin,1,Hỏi Xoáy Đáp Xoay Trên VTV3,1,HTML,1,Huyền Ảo,92,Hướng dẫn Internet cơ bản,1,IFTTT,703,Imgur,2,Infographic,1,Information Disclosure,1,Internet Explorer,3,IT News,39,J2TeaM,29,J2TeaM Tools,9,JavaScript,6,Javascript Injection,3,Juno_okyo's Blog,23,Khóa Học,32,Khóa Học kiếm tiền online với accesstrade,5,khoá học miễn phí,16,Khóa học Photoshop,19,Khóa học sử dụng mã độc và phòng chống mã độc,2,Khoa Huyễn,6,khuyến mãi,16,kiemhiep,9,Kiếm Hiệp,20,Kiếm Tiền MMO,34,kiếm tiền rút gọn link,1,KilerRat,1,Kinh Dị,24,Kinh Dị - Ma,4,Kinh Doanh,73,kinhdi,1,kinhdoanh,5,KRACK Attacks,1,Lãng mạn,1,lazada,1,Lập trình,2,Lịch Sử,5,Linux,1,Local Attack,2,Logins/Cadastro,1,Lỗi Web,1,Lược Sử Hacker,2,Mã Giảm Giá,2,Mã Hóa,48,Malware,3,Master-Code,31,Máy Tính,1,Metasploit,2,Microsoft,4,mobile hacking,2,monero,1,Movie,25,MySQL,1,NEW PRODUCTS,19,NGHỆ THUẬT ẨN MÌNH,13,ngontinh,10,Ngôn Tình,151,nhà đất,1,Nhà Đất Gò Công,1,Nhân Vật Lịch Sử,2,Nhật Bản,1,Nhựt Trường Group,1,NjRat,5,Nước,1,open redirect,1,Oracle,1,Path Disclosure,2,pdf,76,Pen-Test,6,Pentest Box,9,Phan mem Internet,1,phanmem,23,phanmemdienthoai,3,phanmemmaytinh,10,phần mềm,11,Phim 18,2,Phim 2012,1,Phim 3D,1,Phim Âm Nhạc,2,Phim Bộ,39,Phim Chiến Tranh,5,Phim Dã Sử - Cổ Trang,6,Phim Đài Loan,6,Phim Đề Cử,4,Phim Hài Hước,26,Phim Hàn Quốc,33,Phim HD Chất Lượng Cao,5,Phim Hoạt Hình,2,Phim Hot,1,Phim Hồng Kông,20,Phim HQ,2,Phim Kinh Dị,8,Phim lẻ,4,Phim Mới 2011,2,Phim Mới 2012,1,Phim Mới 2015,1,Phim Nhật Bản,4,Phim SD,3,Phim Thái Lan,6,Phim Thần Thoại,4,Phim Tình Cảm,35,Phim Trung Quốc,37,Phim Truyền Hình,19,Phim Viễn Tưởng,1,Phim Võ Thuật,36,Phim Xã Hội Đen,1,Phishing,5,PHP,16,Plugin,1,Port,1,post mẫu,1,prc,77,Programming,15,Python,1,Quảng Cáo,1,rat,457,Recovery,3,Remote Code Execution,1,Remote Desktop,1,Reverse Engineering,6,review,3,rút gọn link,1,sach,47,Sách,35,Sách Nghệ Thuật Sống,12,sách nói,1,Sách Tâm Linh,1,Sách Tiếng Anh,2,sachiep,2,Sản Phẩm,1,Sắc Hiệp,16,Scam,1,Scanner,10,Security,66,SEO,5,share,1,Shell,5,shop,1,Social Engineering,4,Software,22,Source Unity,1,SQL injection,21,Sức Khỏe,1,Symlink,3,Tài Chính,1,Tài chính cá nhân,2,Tài Liệu,1,Tản mạn,7,Taudio,2,Tâm lý xã hội,1,tấn công,1,Testador,1,Thái Lan,2,Tham Khảo,3,thamkhao,11,them,1,Thiệp Cưới,1,Thiết Kế Web,30,Thời Trang,2,Thủ Thuật Hacking,53,Thuyết Minh,1,tienhiep,5,Tiên Hiệp,123,Tiểu Thuyết,94,tiki,3,TIL,8,Tin Tức,52,Tips,39,tool,1,Tool Hack,14,Tools,9,Tổng Hợp,1,Tricks,26,Trinh thám,1,trojan original,48,Trọng sinh,11,Trộm mộ,1,Trung Quốc,1,Truyện,1,Trương Định,110,Tu Chân,2,TUTORIALS,124,Twitter,1,Ung_Dung,4,Upload,1,usb,1,vanhoc,11,văn học,6,vBulletin,7,video,16,Vietsub,1,Việt Nam,4,Virus,4,Võ Thuật,3,Võng Du,5,Vulnerability,19,Web Developer,15,webmau,5,WHMCS,3,WiFi,2,wiki lỗi máy tinh,1,wiki lỗi NTG,3,Windows,12,WordPress,43,Write-up,11,XSS,16,Yahoo,1,yeah1offer,1,youtube,11,
ltr
item
Nhựt Trường - Chia sẻ kiến thức miễn phí: Giới thiệu về thuật toán tham lam - Greedy Algorithm(Phần 2)
Giới thiệu về thuật toán tham lam - Greedy Algorithm(Phần 2)
https://whitehat.vn/filedata/fetch?id=60463&d=1478489406
Nhựt Trường - Chia sẻ kiến thức miễn phí
https://www.nhuttruong.com/2016/11/gioi-thieu-ve-thuat-toan-tham-lam.html
https://www.nhuttruong.com/
https://www.nhuttruong.com/
https://www.nhuttruong.com/2016/11/gioi-thieu-ve-thuat-toan-tham-lam.html
true
7607280272436897486
UTF-8
Loaded All Posts Not found any posts VIEW ALL Readmore Reply Cancel reply Delete By Home PAGES POSTS View All RECOMMENDED FOR YOU LABEL ARCHIVE SEARCH ALL POSTS Not found any post match with your request Back Home Sunday Monday Tuesday Wednesday Thursday Friday Saturday Sun Mon Tue Wed Thu Fri Sat January February March April May June July August September October November December Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec just now 1 minute ago $$1$$ minutes ago 1 hour ago $$1$$ hours ago Yesterday $$1$$ days ago $$1$$ weeks ago more than 5 weeks ago Followers Follow THIS PREMIUM CONTENT IS LOCKED STEP 1: Share to a social network STEP 2: Click the link on your social network Copy All Code Select All Code All codes were copied to your clipboard Can not copy the codes / texts, please press [CTRL]+[C] (or CMD+C with Mac) to copy Table of Content