\(\color{

ff0000}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{

ff0000}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{

ff0000}{\text{Mình xin rút kinh nghiệm và chấn chỉnh bản thân nếu trong editorial có gì sai sót, và bạn có thể gửi feedback }}\) ở đây

---

---

\(\color{

300000}{\text{Hint 1 }}\)

• Thử từng dãy con một và tính tổng khối lượng \(sum\_weight\) và tổng giá trị \(sum\_value\)

  Mỗi cặp \((weight_i, value_i)\) có thể chọn hoặc là không, nên có 2 cách tất cả, với số lượng được lấy là \(x_i \in \{0/1\}\)

Gọi \(S\) là tập hợp con các vị trí \(i\) mà \(x_i = 1\) mình đang xét với độ dài \(k \in [0, n]\)

\(sum\_weight(S) = \underset{i \in S}{\Sigma} weight_i\)

\(sum\_value(S) = \underset{i \in S}{\Sigma} value_i\)

• \(res = max(sum\_value(S))\) thỏa \(sum\_weight(S) \leq W\)
• Tổng số cách chọn là \(2^n\) hay có tất cả \(2^n\) tập S cần xét nên độ phức tạp thời gian là \(\Theta(2^n)\)

  Cải thiện bằng \(\color{

  300000}{\text{}}\) ta có thể bỏ các trường hợp \(sum\_weight\) đang xét lớn hơn \(W\)

Cải thiện bằng \(\color{

300000}{\text{}}\) ta có thể tính giá trị tiếp theo nhanh hơn từ bài toán con trước khi xét cặp \(i\)

---

\(\color{

300000}{\text{Hint 2 }}\)

• Gọi \(f[i][w]\) là giá trị lớn nhất chọn được từ các túi \(a_1 \dots a_i\) với khối lượng không quá \(w\)
• Nhận xét:

  [1] \(f[i][0] = 0 \forall i \in [0, n]\) vì khi không lấy gì \(sum\_weight = sum\_value = 0\). Hay lấy tập rỗng (\(0\) phần tử) thì không tốn gì (không tốn quá \(0\) không gian chứa)

[2] \(f[j][w] \leq f[i][w] \forall j \leq i\) vì việc lấy thêm phần tử khi có thể (tổng không quá \(w\)) luôn làm mình có lợi hơn (vì \(value_i \geq 0\)) [3] \(f[i][c] \leq f[i][w] \forall c \leq w\) vì việc có thêm không gian chứa sẽ có thể lấy thêm phần tử tốt hơn hoặc nhiều phần tử hơn [4] \(f[i][w]\) sẽ phụ thuộc vào \(f[i - 1][c]\) với \(c \in [0, w]\) khi xét cặp thứ \(i\) (dựa vào [2] và [3] thì \(f[i][w]\) là tối ưu tới hiện tại)

• Để tính \(f[i][w]\) ta xét cặp \((weight_i, value_i)\)

  Nếu ta không chọn cặp này, hoặc không thể chọn cặp này (\(w < weight_i\) thì không có balo nào đủ chứa nó). Thì giá trị balo hiện tại là như trước khi xét cặp này \(f[i - 1][w]\) (theo [4])

Nếu ta chọn cặp này. Thì balo trước đó phải đủ chứa \(weight_i\) là các balo \(f[i][0 \dots w - weight_i]\) và ba lô giá trị lớn nhất là \(f[i][w - weight_i]\) (theo [3]) và thêm vào một giá trị từ cặp \(i\) là \(value_i\)

• Vậy ta có công thức

  \(f[i][w] = f[i - 1][w]\) khi \(w < weight_i\)

\(f[i][w] = max(f[i - 1][w], f[i - 1][w - weight_i] + value_i)\) khi \(w \geq weight_i\)

• Kết quả bài toán là \(res = f[n][capacity]\) với \(capacity = W\) là sức chứa của ba lô

---

\(\color{

009933}{\text{Preference Accepted Code }}\): Quy hoạch động

\({{\color{

7f5f3f}{\text{Complexity : }} O(n \times capacity)\ \color{

7f5f3f}{\text{time}}\ ||\ O(n + capacity)\ \color{

7f5f3f}{\text{memory}}}}\)

Xin chào các bạn ở bài viết về QUI HOẠCH ĐỘNG phần 1:https://viblo.asia/p/phan-1thuat-toan-quy-hoach-dong-QpmleJzM5rd mình đã nói qua về qui hoạch động với những ví dụ đơn giản dễ hiểu.

Hôm nay mình xin đề cập đến một bài toán phức tạp hơn: Bài toán cái túi (Knapsack Problem)

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

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

Mô tả bài toán

-Knapsack Problem là bài toán tên chộm mang theo một cái túi có dung lượng nhất định. Mục đích của tên chộm là chất đồ vật sao cho tổng trọng lượng không vượt quá dung lượng của cái túi và tổng giá trị lấy được là lớn nhất.

Cụ thể :

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

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

Tìm cách chất các đồ vật này vào cái túi có dung lượng là b sao cho tổng trọng lượng của các đồ vật được chất vào túi là không quá b, đồng thời tổng giá trị của chúng là lớn nhất.

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

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

• Phân rã: Với các giá trị i (1..n) và i`0 `i`1 Gọi`i`2 là tổng giá trị lớn nhất có thể chọn trong `i đồ vật (từ i`4 đến `i) với trọng lượng tối đa của túi là `i`0. Khi đó `i`7 là giá trị lớn nhất mang đi được.

• Giải bài toán con: i`8 với mọi `i`0, và`W_i`0 với mọi `i.

• Tổng hợp:

• Đã có `W_i`2: Giá trị lớn nhất mang đi được với `W_i`3 đồ vật khi trọng lượng túi là `i`0.
• Xét đồ vật thứ i khi trọng lượng túi vẫn là i`0: Chỉ mang thêm đồ vật thứ `i khi giá trị của túi lúc mang W_i`3 đồ vật ở trọng lượng túi là `W_i`8 (như thế mới đảm bảo mang thêm được đồ vật i có trọng lượng `W_i khi trọng lượng túi là i`0 ) cộng với giá trị của đồ vật thứ `i, C_i`2 lớn hơn khi không mang đồ vật thứ `i, `W_i`2. Bạn suy nghĩ 1 lúc phần này là ra ngay mà
• Nghĩa là:MaxV(i,L)=MaxMaxV(i−1,L−w[i])+c[i],MaxV(i−1,L)MaxV(i, L) = Max{MaxV(i-1,L-w[i])+c[i], MaxV(i-1,L)} tường minh quá rồi nhỉ :v

Giải thuật

    Procedure Bag_best
    {
    For L= 0 to b do MaxV[0,L] =0 ;
    For i= 0 to n do MaxV[i,0] =0 ;
    For i = 1 to n do
        For L = 1 to b do {
    MaxV[i,L] = MaxV[ i-1,L];
    If [(L >= w[i]) && (MaxV[i-1,L-w[i]]+c[i] > MaxV[i-1, L])]
    MaxV[i, L] = MaxV[i-1,L-w[i]]+c[i] ;
    }
    return MaxV(n, b) ;
    }

Một ví dụ cụ thể

Cho 6 đồ vật (n = 6), và túi có trọng lượng b = 19. Các đồ vật có trọng lượng và giá trị như sau:

-Khởi tạo: MaxV[0,L] =0 , MaxV[i,0] =0

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

-Lặp đến hết ta được kết quả :

• Những vật được mang đi: {2, 3, 6}
• Tổng trọng lượng vật: 18
• Tổng giá trị: 70

Kết luận

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

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

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

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

• Tổng hợp lời giải của các bài toán con kích thước nhỏ hơn để thành lời giải bài toán lớn hơn.

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