Phân tích và tiếp cận bài toán Quy hoạch động
algorithm
33
White

Huy Trần viết ngày 27/12/2017

Với sự hỗ trợ của anh @linxGnu (là dân competitive programming thứ thiệt [1] ) cùng với các anh em trong nhóm #algorithm [2] của Cộng đồng Ruby Việt Nam, mình (là dân copypáste programming thứ thiệt) tổng hợp lại qua các trao đổi, thảo luận, nhằm mục đích giới thiệu với bạn đọc các dạng thuật toán thường gặp và cách phân tích, tiếp cận các dạng bài đó.


Bài đầu tiên của series, chúng ta nghiên cứu về một kĩ thuật khá phổ biến và cũng khá là "xương", đó là phương pháp Quy hoạch động (Dynamic Programming), thông qua một bài tập trên Leetcode.

Đó là bài Delete and Earn, tại địa chỉ https://leetcode.com/problems/delete-and-earn/description/

Problem

Cho một mảng số nguyên $\texttt{nums}$, bạn có thể thực hiện những thao tác sau đây trên mảng:

  • Chọn một số $\texttt{nums[i]}$ bất kỳ thì để kiếm được $\texttt{nums[i]}$ điểm.
  • Đồng thời cũng phải xóa đi tất cả các giá trị $\texttt{nums[i] - 1}$ hoặc $\texttt{nums[i] + 1}$ ngay sau đó.

Ban đầu bạn có 0 điểm, cho biết số điểm cao nhất mà bạn có thể kiếm được.

Ví dụ 1:

Input: nums = [3, 4, 2]
Output: 6

Chọn 4 để kiếm 4 điểm, như vậy 3 sẽ bị xóa.
Tiếp theo, chọn 2 để kiếm 2 điểm. Như vậy tổng cộng kiếm được 6 điểm.

Ví dụ 2:

Input: nums = [2, 2, 3, 3, 3, 4]
Output: 9

Đầu tiên, chọn 3 để kiếm được 9 điểm, như vậy tất cả các phần tử có giá trị
2 và 4 đều sẽ bị xóa.

Lưu ý:

  • Độ dài tối đa của $\texttt{nums}$ là $20000$.
  • Mỗi phần tử $\texttt{nums[i]}$ là một số nguyên trong phạm vi $[1, 10000]$.

Solution

Ta thấy, mỗi khi chọn tất cả các phần tử có giá trị $\texttt{nums[i]}$ để cộng vào tổng điểm, thì ta không thể chọn các phần tử có giá trị $\texttt{nums[i] + 1}$ hay $\texttt{nums[i] - 1}$ được nữa, nên phải xóa nó đi (cái này hay gọi là ăn không được thì đạp đổ đấy).

Đề bài bảo tìm giá trị lớn nhất có thể có của tổng điểm, tức là dạng tìm giá trị tối ưu, theo như kinh nghiệm trận mạc, ta có thể giải nó bằng phương pháp Quy hoạch động.

Đối với một giá trị $x$ bất kỳ, ta có $F(x)$ là tổng điểm lớn nhất mà ta có thể thu được, có hai trường hợp có thể xảy ra:

  • Trường hợp 1: Chọn $x$ để cộng vào tổng.

Để dễ hình dung, thì ta lấy giá trị $x$ lớn nhất có thể có mà đề bài cho luôn, là số $x = 10000$. Khi đó, số điểm mà ta sẽ được cộng thêm là $10000 * n$, với $n$ là số lượng các phần tử có cùng giá trị $10000$ ở trong mảng. Đồng thời, ta phải xóa đi tất cả các phần tử có giá trị lân cận, đó là $9999$.

Như vậy, tổng điểm lớn nhất mà chúng ta có thể thu được đối với giá trị $10000$, chính là $10000 * n$ cộng với tổng điểm lớn nhất mà chúng ta có thể thu được với giá trị $9998$ (không có $9999$ vì nó đã bị xóa rồi).

$$
F(10000) = F(9998) + (10000 * n)
$$

Giá trị của $F(9998)$ là bao nhiêu thì chúng ta vẫn chưa biết. Cứ để đó đã.

  • Trường hợp 2: Không chọn $x = 10000$ để cộng vào tổng. Khi đó chắc chắn chúng ta sẽ phải chọn một giá trị lân cận của $x$, đó là $9999$.

$$
F(10000) = F(9999)
$$

Việc chọn trường hợp 1 hay 2 tùy thuộc vào kết quả tốt nhất mà nó mang lại, ở đây là trường hợp nào cho kết quả lớn hơn:

$$
F(10000) = max\Big(F(9999), F(9998) + (10000 * n)\Big)
$$

Thế là ta đã tìm được công thức truy hồi để tính $F(10000)$ từ $F(9999)$ và $F(9998)$. Hay viết tổng quát ra thành:

$$
F(x) = max\Big(F(x-1), F(x-2) + x * count(x)\Big)
$$

Implementation

Có công thức truy hồi rồi thì ta dễ dàng implement được thuật toán để giải bài này. Sau đây là bài giải bằng JavaScript của mình, và bằng Golang của anh linxGnu.

Mấu chốt của việc giải một bài toán Quy hoạch động chính là việc tìm ra công thức truy hồi, hoặc dạng đệ quy của bài toán (thường là thể hiện tính chất của bài toán từ phương án tổng quát đến cụ thể - top-down), sau đó, ta chỉ việc implement lại công thức đó theo thứ tự ngược lại (từ trường hợp cụ thể đến tổng quát - bottom-up) [3].

JavaScript

const deleteAndEarn = (nums) => {
  if (!nums.length) {
    return 0;
  }

  let maxPossible = 10000;

  let points = Array.from(Array(maxPossible + 1)).map(x => 0);
  for (let i = 0; i < nums.length; i++) {
    points[nums[i]] += nums[i];
  }

  let F = Array.from(Array(maxPossible + 1)).map((x, i) => points[i]);
  for (let i = 2; i <= maxPossible; i++) {
    F[i] = Math.max(F[i-1], F[i-2] + points[i]);
  }

  return F[maxPossible];
};

Bài giải bằng Golang có sử dụng một vài trick khá hay.

Golang

func deleteAndEarn(nums []int) int {
    if nums == nil || len(nums) == 0 {
        return 0
    }

    // use counter sort instead
    counter := make([]int, 10001)
    for _, v := range nums {
        counter[v]++
    }

    // using counter for Dynamic Programing formula
    // f[i] = max(f[i-2] + counter[i] * i, f[i-1])
    if counter[2] <<= 1; counter[2] < counter[1] {
        counter[2] = counter[1]
    }
    for i := 3; i <= 10000; i++ {
        if counter[i] = counter[i-2] + counter[i] * i; counter[i] < counter[i-1] {
            counter[i] = counter[i-1]
        }
    }

    return counter[10000]
}

Comments

Thay cho phần kết luận, mình xin trích dẫn một vài ý từ cuốn The Algorithm Design Manual về Quy hoạch động mà mình cho là rất có ích:

  • Dynamic programming is best learned by carefully studying examples until things start to click.
  • Ultil you understand dynamic programming, it seems like magic.
  • You must figure out the trick before you can use it.

Và đây là trick:

  • Dynamic programming is a technique for efficiently implementing a recursive algorithm by storing partial results.
  • The trick is: seeing whether the naive recursive algorithm computes the same subproblems over and over again.
  • If so, storing the answer for each subproblem in a table to lookup instead of recomputing.
  • Start with a recursive algorithm or definition. Only once we have a correct recursive algorithm, do we worry about speeding it up by using a result matrix.

Notes

  • [1] Nghe đồn ông này từng đi ra đề thi quốc gia lận đó. Nguồn: tin đồn
  • [2] Nhóm này có rule rất đáng ghét, ví dụ như trong 1 tuần mà ông nào không làm bài thì coi như mất toi 10 USD, trích từ rule của nhóm. Không nghiêm túc thì không tiến bộ được.
  • [3] Nên đọc thêm Chương 8 của quyển The Algorithm Design Manual, phần giới thiệu về Dynamic Programming có nói rất rõ về tính chất này và rất dễ hiểu.
  • [4] Bài đăng lại từ blog của mình
Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

Huy Trần

115 bài viết.
1763 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
167 46
Tại sao phải viết blog kĩ thuật? Có rất nhiều bài viết trên mạng nói về vấn đề tại sao một lập trình viên nên thường xuyên viết các bài blog kĩ thu...
Huy Trần viết hơn 3 năm trước
167 46
White
151 39
(Ảnh) Tiếp tục sêri (Link) lần này, chúng ta sẽ cùng tìm hiểu và mô phỏng lại một chức năng mà mọi người đang bắt đầu sử dụng hằng ngày, đó là chứ...
Huy Trần viết hơn 2 năm trước
151 39
White
108 17
Phần 1: Tự truyện Tui và Toán đã từng là hai kẻ thù không đội trời chung trong suốt hơn mười lăm năm ròng rã. Ngay từ ánh nhìn đầu tiên đã ghét nh...
Huy Trần viết hơn 2 năm trước
108 17
Bài viết liên quan
White
44 7
Là một người thường xuyên đọc Quora, có một điểm cá nhân tôi thấy rất ấn tượng ở quora chính là khả năng autocomplete với tốc độ ánh sáng. (Ảnh) ...
huydx viết 10 tháng trước
44 7
White
3 0
What is competitive programming? Sites like CodeForces, TopCoder, HackerRank, CodeChef,... ACMICPC, Olympiad in Informatics (for high school stude...
Nguyễn Lê Vũ Long viết hơn 1 năm trước
3 0
White
76 34
Bài viết thuộc chủ đề nghiên cứu trong nhóm hardcore của Cộng đồng Ruby Việt Nam Đọc manga trên mobile là một nhu cầu rất lớn, nhưng hiện nay chư...
Huy Trần viết gần 2 năm trước
76 34
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
115 bài viết.
1763 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!