GIẢI BÀI TOÁN CÁI TÚI ) VỚI C++, GIẢI THUẬT VÀ LẬP TRÌNH: §3

  -  
Thuật toán QUI HOẠCH ĐỘNG phần 2

Xin chào chúng ta ở bài viết về QUI HOẠCH ĐỘNG phần 1:https://6struyenky.vn/p/phan-1thuat-toan-quy-hoach-dong-QpmleJzM5rd tôi đã nói qua về qui hoạch đụng với số đông ví dụ đơn giản dễ dàng dễ hiểu.

Bạn đang xem: Giải bài toán cái túi ) với c++, giải thuật và lập trình: §3

Hôm nay bản thân xin đề cập đến một bài toán phức tạp hơn: vấn đề cái túi (Knapsack Problem)

Đây chỉ là một trong những bài toán bé dại để các bạn cũng có thể vận dụng được những việc khó rộng hãy làm để hiểu thuần thục nó nhé.

Câu thần chú: Phân tung - Giải việc con - Tổng hợp bài toán con thành việc lớn

Mô tả bài xích toán

-Knapsack Problem là vấn đề tên chộm sở hữu theo một cái túi có dung lượng nhất định. Mục tiêu của tên chộm là hóa học đồ vật làm sao cho tổng trọng lượng không vượt quá dung tích của loại túi và tổng mức vốn lấy được là bự nhất.

Cụ thể :

Có n vật dụng vật, đồ vật i có trọng lượng W_i và cực hiếm C_i

với i=1,2,...,ni = 1, 2, ..., ni=1,2,...,n.

Tìm cách chất các đồ đồ dùng này vào cái túicó dung lượng là b sao để cho tổng trọnglượng của các đồ vật được hóa học vào túi làkhông vượt b, đồng thời tổng mức vốn củachúng là bự nhất.

Đi tìm giải mã bằng thuật toán qui hoạch động

Có: n - Số thứ vật, b - trọng lượng túi (lấy giá trị nguyên)

• Phân rã: Với những giá trị i (1..n) với L (0..b) GọiMaxV(i,L) là tổng giá trị lớn nhất hoàn toàn có thể chọntrong i đồ vật (từ 1 đến i) cùng với trọng lượng tốiđa của túi là L. Khi đó MaxV(n,b) là cực hiếm lớnnhất đưa đi được.

Xem thêm: Giảm Giá Thẻ Đổi Tên Và Tăng Điểm! (24/02, Điều Kiện, Nền Tảng & Điều Bắt Buộc Của Salah

• Giải việc con: MaxV(0,L) = 0 với mọi L, vàMaxV(i,0) = 0 với mọi i.

• Tổng hợp:

Đã có MaxV(i-1,L): giá trị béo nhất mang đi đượcvới i-1 đồ vật khi trọng lượng túi là L.

Xét dụng cụ thứ i lúc trọng lượng túi vẫn luôn là L: Chỉ có thêm dụng cụ thứ i khi giá trị của túi lúc mang i-1 dụng cụ ở trọng lượng túi là L - w * i (như thế mới đảmbảo mang thêm được dụng cụ i tất cả trọng lượng W_i khitrọng lượng túi là L )cộng với giá trị của dụng cụ thứ i, c to hơn khi không mang dụng cụ thứ i, MaxV(i-1,L). Bạn để ý đến 1 lúc phần này là ra ngay cơ mà

*

-Khởi tạo: MaxV<0,L> =0 , MaxV =0

*

-Lặp : 2 vòng lặp như lời giải ở trên

*

*

*

-Lặp đến khi kết thúc ta được công dụng :

*

*

Những vật dụng được với đi: 2, 3, 6

Tổng trọng lượng vật: 18

Tổng giá bán trị: 70

Kết luận

Công thức thần thánh là dây:

-Phân rã: Chia câu hỏi cần giải thành những bài toán con nhỏ dại hơn mang lại mức có thể giải trực tiếp được tuyệt không?Nếu giải được chuyển sang bước giải câu hỏi con.

-Giải các bài toán bé và ghi thừa nhận lời giải: lưu trữ lời giải của những bài toán con vào một trong những bảng để áp dụng về sau.

Xem thêm: Cách Xác Định Các Dạng Khuôn Mặt Nam Giới Để Chọn Kiểu Tóc Phù Hợp

-Tổng đúng theo lời giải:

Tổng vừa lòng lời giải của những bài toán nhỏ kích thước nhỏ tuổi hơn để thành giải mã bài toán lớn hơn.

tiếp tục như vậy cho tới khi thu được giải thuật của việc xuất vạc (là việc con có kích thước lớn nhất)