Tại sao thuật toán tham lam lại tối ưu?

Question

Tính linh hoạt, bài 14, công việc TieRopes (https://codility.com/demo/take-sample-test/tie_ropes). Nói một cách ngắn gọn, vấn đề là để phân vùng một danh sách A của các số nguyên dương vào số lượng tối đa (tiếp giáp) danh sách con có tổng ít nhất K.

Tôi chỉ đưa ra giải pháp tham lam vì đó là tên của bài học. Nó vượt qua tất cả các bài kiểm tra nhưng tôi không biết tại sao nó là một giải pháp tối ưu (nếu nó là tối ưu ở tất cả).

int solution(int K, vector<int> &A) { 
    int sum = 0, count = 0; 
    for (int a : A) 
    { 
     sum += a; 
     if (sum >= K) 
     { 
      ++count; 
      sum = 0; 
     } 
    } 
    return count; 
} 

Ai đó có thể cho tôi biết nếu và tại sao giải pháp này là tối ưu?

Answer 1

Có lẽ tôi đang ngây thơ hoặc mắc sai lầm ở đây, nhưng tôi nghĩ rằng đó không phải là quá khó (mặc dù không rõ ràng) để thấy rằng thuật toán thực sự là tối ưu.

Giả sử bạn có phân vùng tối ưu của danh sách có số lượng danh sách phụ tối đa. Bạn có thể hoặc không có tất cả các phần tử trong danh sách, nhưng vì việc thêm một phần tử vào danh sách hợp lệ sẽ tạo ra một danh sách hợp lệ, giả sử rằng bất kỳ phần tử "còn lại" nào ban đầu không được gán cho bất kỳ danh sách con nào được gán tùy ý một trong các danh sách con liền kề của nó; vì vậy chúng tôi có phân vùng tối ưu thích hợp của danh sách, chúng tôi sẽ gọi P1.

Bây giờ hãy nghĩ về phân vùng mà thuật toán tham lam sẽ tạo ra, nói P2. Có hai điều có thể xảy ra cho sublist đầu tiên trong P2:

1. Nó có thể giống như các sublist đầu tiên trong P1.
2. Nó có thể ngắn hơn danh sách con đầu tiên trong P1.

Trong 1. bạn sẽ lặp lại lý do bắt đầu trong phần tử tiếp theo sau danh sách con đầu tiên. Nếu mỗi danh sách con tiếp theo được tạo ra bởi thuật toán bằng với P1, thì P1 và P2 sẽ bằng nhau.

Trong 2. bạn cũng sẽ lặp lại lý do, nhưng bây giờ bạn có ít nhất một mục "phụ" khả dụng. Vì vậy, một lần nữa, danh sách phụ tiếp theo có thể:

2.1. Nhận được như xa như các sublist tiếp theo trong P1.
2.2. Kết thúc trước danh sách con tiếp theo trong P1.

Và lặp lại. Vì vậy, trong mọi trường hợp, bạn sẽ có ít nhất ít nhất là nhiều danh sách con dưới dạng P1. Có nghĩa là, P2 là ít nhất là tốt như mọi phân vùng có thể có trong danh sách và đặc biệt là bất kỳ phân vùng tối ưu nào.

Nó không phải là một cuộc biểu tình rất chính thức, nhưng tôi nghĩ rằng nó hợp lệ. Hãy chỉ ra bất cứ điều gì bạn nghĩ có thể sai.

Answer 2

Dưới đây là các ý tưởng dẫn đến bằng chứng chính thức.

1. Nếu A là một hậu tố của B, sau đó kích thước phân vùng tối đa cho A là nhỏ hơn hoặc bằng với kích thước phân vùng tối đa cho B, bởi vì chúng ta có thể mở rộng sublist đầu tiên của một phân vùng của A để bao gồm các yếu tố mới mà không làm giảm tổng của nó.

2. Mọi tiền tố thích hợp của mỗi danh sách con trong tổng giải pháp tham lam đến ít hơn K.

3. Không có điểm trong việc có khoảng trống, vì chúng tôi có thể thêm các phần tử còn thiếu vào danh sách liền kề (tôi nghĩ rằng từ ngữ của câu hỏi đã loại trừ khả năng này theo định nghĩa, nhưng tôi sẽ nói nó).

Các bằng chứng chính thức có thể được thực hiện bằng quy nạp để chứng minh rằng, với mọi số nguyên không âm i, có tồn tại một giải pháp tối ưu mà đồng ý với giải pháp tham lam trên i danh sách con đầu tiên của mỗi. Sau đó, khi i đủ lớn, giải pháp duy nhất đồng ý với tham lam là tham lam, vì vậy giải pháp tham lam là tối ưu.

Cơ sở i = 0 là tầm thường, vì giải pháp tối ưu tùy ý sẽ thực hiện. Bước quy nạp bao gồm việc tìm kiếm giải pháp tối ưu phù hợp với tham số trên danh sách con i đầu tiên và sau đó thu hẹp danh sách con i+1 để phù hợp với giải pháp tham lam (theo quan sát 2, chúng tôi thực sự thu hẹp danh sách con đó, vì nó bắt đầu ở vị trí tương tự như Theo quan sát 1, chúng ta có thể mở rộng danh sách phụ thứ nhất của i+2 của giải pháp tối ưu).