Giải Thuật Và Lập Trình: §3.2. Bài Toán Cái Túi | V1Study

• Đào tạo Độ tuổi từ 5 - 11 Độ tuổi từ 12 - 17 Từ 18 tuổi
• Lập trình Python Lập trình C C++ Java C# - C Sharp Android Scratch Pascal Robot mBot
• Web ReactJS HTML5 CSS3 JavaScript Node.js JSP ASP.NET Core jQuery PHP
• FW-CMS Laravel AngularJS Flutter Magento Bootstrap VueJS CodeIgnitor WordPress Sass Drupal
• Video Video Python Video Lập trình C Video C# Video Java Video HTML5-CSS3-JavaScript Video SQL Server Video PHP Video jQuery Video Android Video C++ Video Scratch
• Video1 Video XML-JSON Video MySQL Video Excel Video Giải thuật và Lập trình Video Sức khỏe Video Drupal Video mBot Video Giáo dục - Khoa học
• Other Unity Giải thuật và lập trình Giải thuật và lập trình - C CCNA Mạng máy tính Design Patterns English Facebook SEO Git Tin học đại cương Japanese App-Uti Download
• Data SQL Server XML JSON MySQL
• News

≡ ≡ Giải thuật và lập trình Phần 1: Bài toán liệt kê Lời mở đầu §1. Nhắc lại một số kiến thức đại số tổ hợp §2. Phương pháp sinh (GENERATION) §3. Thuật toán quay lui §4. Kỹ thuật nhánh cận Phần 2: Cấu trúc dữ liệu và giải thuật Lời mở đầu §1. Các bước cơ bản khi tiến hành giải các bài toán tin học §2. Phân tích thời gian thực hiện giải thuật §3. Đệ quy và giải thuật đệ quy §4. Cấu trúc dữ liệu biểu diễn danh sách §5. Ngăn xếp và hàng đợi §6. CÂY (TREE) §7. Ký pháp tiền tố, trung tố và hậu tố §8.1. Sắp xếp (SORTING) - Phần 1 §8.2. Sắp xếp (SORTING) - Phần 2 §9. Tìm kiếm (SEARCHING) Bài tập phần độ phức tạp giải thuật Bài tập phần Biểu diễn danh sách, Stack và Queue Phần 3: Quy hoạch động Lời mở đầu §1. Công thức truy hồi §2. Phương pháp quy hoạch động §3.1. Dãy con đơn điệu tăng dài nhất §3.2. Bài toán cái túi §3.3. Biến đổi xâu §3.4. Dãy con có tổng chia hết cho K §3.5. Phép nhân tổ hợp dãy ma trận §3.6. Bài tập luyện tập Phần 4: Các thuật toán trên đồ thị Lời mở đầu §1. Các khái niệm cơ bản §2. Biểu diễn đồ thị trên máy tính §3. Các thuật toán tìm kiếm trên đồ thị §4. Tính liên thông của đồ thị §5. Vài ứng dụng của các thuật toán tìm kiếm trên đồ thị §6. Chu trình Euler, đường đi Euler, đồ thị Euler §7. Chu trình Hamilton, đường đi Hamilton, đồ thị Hamilton §8. Bài toán đường đi ngắn nhất §9. Bài toán cây khung nhỏ nhất §10. Bài toán luồng cực đại trên mạng §11. Bài toán tìm bộ ghép cực đại trên đồ thị hai phía §12. Bài toán tìm bộ ghép cực đại với trọng số cực tiểu trên đồ thị hai phía. Thuật toán Hungari §13. Bài toán tìm bộ ghép cực đại trên đồ thị Giải thuật và lập trình: §3.2. Bài toán cái túi Khóa học qua video: Lập trình Python All Lập trình C# All SQL Server All Lập trình C Java PHP HTML5-CSS3-JavaScript Đăng ký Hội viên Tất cả các video dành cho hội viên

Trong siêu thị có n gói hàng (n <= 100), gói hàng thứ i có trọng lượng là Wi <= 100 và trị giá Vi <= 100. Một tên trộm đột nhập vào siêu thị, tên trộm mang theo một cái túi có thể mang được tối đa trọng lượng M ( M <= 100). Hỏi tên trộm sẽ lấy đi những gói hàng nào để được tổng giá trị lớn nhất.

Input: file văn bản BAG.INP

• Dòng 1: Chứa hai số n, M cách nhau ít nhất một dấu cách
• n dòng tiếp theo, dòng thứ i chứa hai số nguyên dương Wi, Vi cách nhau ít nhất một dấu cách

Output: file văn bản BAG.OUT

• Dòng 1: Ghi giá trị lớn nhất tên trộm có thể lấy
• Dòng 2: Ghi chỉ số những gói bị lấy

BAG.INP		BAG.OUT
5	11	11
3	3	5 2 1
4	4
5	4
9	10
4	4

Cách giải:

Nếu gọi F[i, j] là giá trị lớn nhất có thể có bằng cách chọn trong các gói {1, 2, …, i} với giới hạn trọng lượng j, thì giá trị lớn nhất khi được chọn trong số n gói với giới hạn trọng lượng M chính là F[n, M].

3.2.1. Công thức truy hồi tính F[i, j].

Với giới hạn trọng lượng j, việc chọn tối ưu trong số các gói {1, 2, …,i - 1, i} để có giá trị lớn nhất sẽ có hai khả năng:

• Nếu không chọn gói thứ i thì F[i, j] là giá trị lớn nhất có thể 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 là j, tức là F[i, j] = F[i - 1, j]
• 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.

3.2.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.2.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, v.v… đến khi tính hết dòng n.

3.2.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.

P_3_03_3.PAS * Bài toán cái túi

program The_Bag; const InputFile = 'BAG.INP'; OutputFile = 'BAG.OUT'; max = 100; var W, V: Array[1..max] of Integer; F: array[0..max, 0..max] of Integer; n, M: Integer; procedure Enter; var i: Integer; fi: Text; begin Assign(fi, InputFile); Reset(fi); ReadLn(fi, n, M); for i := 1 to n do ReadLn(fi, W[i], V[i]); Close(fi); 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]} 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} var fo: Text; begin Assign(fo, OutputFile); Rewrite(fo); WriteLn(fo, 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 n lên hàng 0} begin if F[n, M] <> F[n - 1, M] then {Nếu có chọn gói thứ n} begin Write(fo, n, ' '); M := M - W[n]; {Đã chọn gói thứ n rồi thì chỉ có thể mang thêm được trọng lượng M - Wn nữa thôi} end; Dec(n); end; Close(fo); end; begin Enter; Optimize; Trace; end. Nguồn: Giáo trình Giải thuật và Lập trình - Lê Minh Hoàng - Đại học sư phạm Hà Nội » Tiếp: §3.3. Biến đổi xâu « Trước: §3.1. Dãy con đơn điệu tăng dài nhất Khóa học qua video: Lập trình Python All Lập trình C# All SQL Server All Lập trình C Java PHP HTML5-CSS3-JavaScript Đăng ký Hội viên Tất cả các video dành cho hội viên Khóa học qua video: Lập trình Python All Lập trình C# All SQL Server All Lập trình C Java PHP HTML5-CSS3-JavaScript Đăng ký Hội viên Tất cả các video dành cho hội viên Copied !!! Copy linkCopied link!

Bạn muốn tìm kiếm điều gì?

×