HƯỚNG DẪN GIẢI BÀI TOÁN CÁI TÚI

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

Xin xin chào chúng ta làm việc nội dung bài viết về QUI HOẠCH ĐỘNG phần 1:https://mbachulski.com/p/phan-1thuat-toan-quy-hoach-dong-QpmleJzM5rd tôi đã cốt truyện về qui hoạch cồn cùng với phần nhiều ví dụ đơn giản và dễ dàng dễ hiểu.

Bạn đang xem: Hướng dẫn giải bài toán cái túi

Hôm nay bản thân xin đề cập tới một bài xích tân oán phức tạp hơn: Bài tân oán dòng túi (Knapsachồng Problem)

Đây chỉ là 1 trong những bài xích tân oán nhỏ dại để những bạn có thể áp dụng được phần nhiều bài toán cạnh tranh rộng hãy làm để gọi thuần thục nó nhé.

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

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

-Knapsack Problem là bài xích tân oán thương hiệu chộm có theo một chiếc túi tất cả dung lượng nhất thiết. Mục đích của tên chộm là chất đồ vật làm thế nào để cho tổng trọng lượng ko quá quá dung lượng của loại túi và tổng mức vốn lấy được là lớn số 1.

Cụ thể :

Có n đồ vật, đồ vật i tất cả trọng lượng W_i cùng cực hiếm C_i

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

Xem thêm: Đề Nghị Bộ Y Tế Sớm Ban Hành Thông Tư Hướng Dẫn Nghị Định 16 Về Tự Chủ

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

Đi kiếm tìm lời giải bằng thuật tân oán qui hoạch động

Có: n - Số đồ vật, b - trọng lượng túi (mang quý giá 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 mức vốn lớn nhất hoàn toàn có thể chọnvào i đồ vật (từ là 1 cho i) với trọng lượng tốinhiều của túi là L. khi đó MaxV(n,b) là quý giá lớnnhất mang đi được.

• Giải bài bác toán thù con: MaxV(0,L) = 0 với đa số L, vàMaxV(i,0) = 0 với mọi i.

• Tổng hợp:

Đã gồm MaxV(i-1,L): Giá trị lớn số 1 mang đi đượccùng với i-1 dụng cụ Lúc trọng lượng túi là L.

Xét đồ vật sản phẩm i lúc trọng lượng túi vẫn chính là L: Chỉ với thêm dụng cụ máy i lúc cực hiếm của túi lúc sở hữu i-1 dụng cụ sinh sống trọng lượng túi là L - w * i (như vậy new đảmbảo có thêm được đồ vật i bao gồm trọng lượng W_i khitrọng lượng túi là L )cùng với mức giá trị của đồ vật trang bị i, c lớn hơn khi không sở hữu đồ vật thiết bị i, MaxV(i-1,L). quý khách Để ý đến 1 lúc phần này là ra ngay mà

*

Nghĩa là:MaxV(i,L)=MaxMaxV(i−1,L−w)+c,MaxV(i−1,L)MaxV(i, L) = MaxMaxV(i-1,L-w)+c, MaxV(i-1,L)MaxV(i,L)=MaxMaxV(i−1,L−w)+c,MaxV(i−1,L) tường minch quá rồi thất thoát :v

Giải thuật

Procedure Bag_best For L= 0 khổng lồ b vì chưng MaxV<0,L> =0 ; For i= 0 to n vị MaxV =0 ; For i = 1 khổng lồ n do For L = 1 lớn b bởi MaxV = MaxV< i-1,L>; If <(L >= w) &và (MaxV>+c > MaxV)> MaxV = MaxV>+c ; return MaxV(n, b) ;

Một ví dụ cầm thể

Cho 6 đồ vật (n = 6), với túi có trọng lượng b = 19. Các dụng cụ tất cả trọng lượng với giá trị nlỗi sau: