Bài Toán Cái Túi C++

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

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

Bạn đang xem: Bài toán cái túi c++

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

Đây chỉ là 1 trong những bài toán nhỏ để các chúng ta có thể vận dụng được những việc khó hơn hãy làm cho để đọc thuần thục nó nhé.

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

Mô tả bài bác toán

-Knapsack Problem là việc tên chộm với theo một chiếc túi có dung tích nhất định. Mục đích của thương hiệu chộm là hóa học đồ vật làm sao cho tổng trọng lượng ko vượt quá dung tích của dòng túi và tổng giá trị lấy được là khủng nhất.

Cụ thể :

Có n trang bị vật, đồ vật i tất cả trọng lượng W_i và giá trị C_i

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

Tìm giải pháp chất các đồ thứ này vào cái túicó dung lượng là b làm thế nào để cho tổng trọnglượng của những đồ đồ gia dụng được chất vào túi làkhông quá b, đồng thời tổng giá trị củachúng là khủng nhất.

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

Có: n - Số vật vật, b - trọng lượng túi (lấy cực hiếm nguyên)

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

Xem thêm: Cháo Cá Hồi Nấu Với Rau Gì Cho Bé Ăn Dặm Được Khuyên Từ Chuyên Gia

• Giải vấn đề con: MaxV(0,L) = 0 với đa số L, vàMaxV(i,0) = 0 với tất cả i.

• Tổng hợp:

Đã tất cả MaxV(i-1,L): giá chỉ trị phệ nhất đưa đi đượcvới i-1 đồ vật khi trọng lượng túi là L.

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

*

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

*

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

*

*

*

-Lặp cho đến khi xong ta được công dụng :

*

*

Những thiết bị được mang đ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 việc cần giải thành những việc con nhỏ hơn mang đến mức có thể giải trực tiếp được giỏi không?Nếu giải được chuyển sang bước giải bài toán con.

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

Xem thêm: Thông Tin Tuyển Sinh Trường Cao Đẳng Sư Phạm Thái Nguyên 2022

-Tổng thích hợp lời giải:

Tổng phù hợp lời giải của những bài toán nhỏ kích thước bé dại hơn nhằm thành giải thuật bài toán lớn hơn.

tiếp tục như vậy cho đến khi thu được giải mã của vấn đề xuất phân phát (là việc con có size lớn nhất)