Lập trình C/C++, Lập trình Python

Tổng lớn nhất của các phần tử không liền kề

Posted on by Đỗ Thành
01
Th4
View: 59

Giới thiệu bài toán

Bài toán “Maximum Sum of Non-adjacent Elements” (tạm dịch là Tổng lớn nhất của các phần tử không liền kề) là một bài toán lập trình thường được đưa ra trong các phỏng vấn kỹ thuật. Nó yêu cầu tìm cách chọn một tập hợp con của các phần tử trong một mảng sao cho tổng của các phần tử đó là lớn nhất, nhưng không có hai phần tử nào trong tập hợp con đó được kề nhau.

Ví dụ, với mảng số nguyên {3, 2, 5, 10, 7}, ta có thể chọn tập hợp con {3, 5, 7} hoặc {2, 10} để có tổng lớn nhất là 15.

Các thuật toán

Có nhiều thuật toán khác nhau để giải quyết bài toán này, bao gồm:

  1. Thuật toán Quy hoạch động:

    • Ta sử dụng một mảng động để lưu trữ tổng lớn nhất có thể đạt được cho tới phần tử thứ i trong mảng.
    • Ta tính toán giá trị cho mỗi phần tử trong mảng động dựa trên giá trị của phần tử đó và giá trị tối đa của các phần tử không kề nhau trước đó.
    • Sau khi tính toán xong, ta trả về giá trị lớn nhất trong mảng động.

  2. Thuật toán Đệ quy:

    • Ta tính toán tổng lớn nhất có thể đạt được bằng cách chọn hoặc bỏ qua từng phần tử trong mảng.
    • Với mỗi phần tử, ta tính toán tổng lớn nhất có thể đạt được bằng cách bỏ qua nó hoặc chọn nó và bỏ qua phần tử kề cận trước đó.
    • Sau khi xử lý hết mảng, ta trả về tổng lớn nhất có thể đạt được.

  3. Thuật toán Tham lam:

    • Ta duyệt qua từng phần tử trong mảng và lưu trữ hai giá trị: tổng lớn nhất có thể đạt được nếu chọn phần tử đó và tổng lớn nhất có thể đạt được nếu bỏ qua phần tử đó.
    • Với mỗi phần tử, ta tính toán hai giá trị này dựa trên tổng lớn nhất có thể đạt được của phần tử trước đó.
    • Sau khi xử lý hết mảng, ta trả về tổng lớn nhất có thể đạt được.

Đánh giá độ phức tạp của các thuật toán

Độ phức tạp của các thuật toán giải quyết bài toán Maximum Sum of Non-adjacent Elements như sau:

  1. Thuật toán Quy hoạch động:
  • Độ phức tạp thời gian: O(n), với n là số lượng phần tử trong mảng. Việc tính toán giá trị cho mỗi phần tử trong mảng động mất O(1) thời gian, và ta cần tính toán giá trị cho tất cả các phần tử trong mảng động.
  • Độ phức tạp không gian: O(n), vì ta cần một mảng động có độ dài bằng số lượng phần tử trong mảng.
  1. Thuật toán Đệ quy:
  • Độ phức tạp thời gian: O(2^n), với n là số lượng phần tử trong mảng. Việc tính toán tổng lớn nhất có thể đạt được cho từng phần tử trong mảng mất O(2^n) thời gian trong trường hợp xấu nhất (khi ta phải kiểm tra tất cả các tập hợp con có thể có).
  • Độ phức tạp không gian: O(n), vì ta cần một stack để lưu trữ các phần tử được chọn.
  1. Thuật toán Tham lam:
  • Độ phức tạp thời gian: O(n), với n là số lượng phần tử trong mảng. Việc tính toán tổng lớn nhất có thể đạt được cho từng phần tử trong mảng mất O(1) thời gian, và ta cần tính toán giá trị cho tất cả các phần tử trong mảng.
  • Độ phức tạp không gian: O(1), vì ta chỉ cần lưu trữ hai giá trị cho mỗi phần tử.

Tóm lại, thuật toán Quy hoạch động có độ phức tạp thấp nhất và là thuật toán tối ưu để giải quyết bài toán Maximum Sum of Non-adjacent Elements. Các thuật toán Đệ quy và Tham lam cũng có thể giải quyết bài toán này, nhưng độ phức tạp của chúng cao hơn nhiều so với thuật toán Quy hoạch động.

Cài đặt các thuật toán

Cài đặt Thuật toán Quy hoạch động với Python

 

def maxSubsetSumNoAdjacent(array):
    if not array:
        return 0
    if len(array) == 1:
        return array[0]
    
    maxSums = array[:]
    maxSums[1] = max(array[0], array[1])
    for i in range(2, len(array)):
        maxSums[i] = max(maxSums[i - 1], maxSums[i - 2] + array[i])
    
    return maxSums[-1]

Giải thích:

  • Nếu danh sách trống, ta trả về 0. Nếu danh sách chỉ có một phần tử, ta trả về giá trị của phần tử đó.
  • Tạo một danh sách maxSums có cùng độ dài và giá trị với danh sách đầu vào. Giá trị của maxSums[i] là tổng lớn nhất có thể đạt được tính từ các phần tử trước đó và bao gồm phần tử i.
  • Thực hiện vòng lặp từ i = 2 đến len(array) – 1. Tại mỗi vòng lặp, ta tính toán tổng lớn nhất có thể đạt được tính từ các phần tử trước đó, bao gồm phần tử i, bằng cách so sánh maxSums[i-1] và maxSums[i-2] cộng với array[i]. Ta lưu kết quả này vào maxSums[i].
  • Trả về giá trị của maxSums[-1], tức là tổng lớn nhất có thể đạt được mà không có hai phần tử nào liền kề được chọn.

Cài đặt Thuật toán Quy hoạch động với C++

#include <vector>

int maxSubsetSumNoAdjacent(std::vector<int> array) {
    if (array.empty()) {
        return 0;
    }
    if (array.size() == 1) {
        return array[0];
    }
    
    std::vector<int> maxSums = array;
    maxSums[1] = std::max(array[0], array[1]);
    for (int i = 2; i < array.size(); i++) {
        maxSums[i] = std::max(maxSums[i - 1], maxSums[i - 2] + array[i]);
    }
    
    return maxSums.back();
}

Giải thích:

  • Nếu danh sách trống, ta trả về 0. Nếu danh sách chỉ có một phần tử, ta trả về giá trị của phần tử đó.
  • Tạo một vector maxSums có cùng độ dài và giá trị với vector đầu vào. Giá trị của maxSums[i] là tổng lớn nhất có thể đạt được tính từ các phần tử trước đó và bao gồm phần tử i.
  • Thực hiện vòng lặp từ i = 2 đến size() – 1. Tại mỗi vòng lặp, ta tính toán tổng lớn nhất có thể đạt được tính từ các phần tử trước đó, bao gồm phần tử i, bằng cách so sánh maxSums[i-1] và maxSums[i-2] cộng với array[i]. Ta lưu kết quả này vào maxSums[i].
  • Trả về giá trị của maxSums.back(), tức là tổng lớn nhất có thể đạt được mà không có hai phần tử nào liền kề được chọn.

Cài đặt Thuật toán Đệ quy với Python

def maxSubsetSumNoAdjacent(array):
    if not array:
        return 0
    if len(array) == 1:
        return array[0]
    if len(array) == 2:
        return max(array[0], array[1])
    
    return max(maxSubsetSumNoAdjacent(array[:-1]), maxSubsetSumNoAdjacent(array[:-2]) + array[-1])

Giải thích:

  • Nếu danh sách trống, ta trả về 0. Nếu danh sách chỉ có một phần tử, ta trả về giá trị của phần tử đó.
  • Nếu danh sách có hai phần tử, ta trả về giá trị lớn hơn trong hai phần tử đó.
  • Nếu danh sách có ba phần tử trở lên, ta tính toán tổng lớn nhất có thể đạt được với các phần tử từ đầu đến phần tử thứ N-1 bằng cách sử dụng đệ quy và trả về giá trị lớn hơn trong hai kết quả sau đây:
    • Tổng lớn nhất có thể đạt được với các phần tử từ đầu đến phần tử thứ N-2.
    • Tổng lớn nhất có thể đạt được với các phần tử từ đầu đến phần tử thứ N-3 cộng với phần tử thứ N-1.

Cài đặt Thuật toán Đệ quy với C++

#include <vector>
#include <algorithm>
using namespace std;

int maxSubsetSumNoAdjacent(vector<int>& array) {
    int n = array.size();
    if (n == 0) return 0;
    if (n == 1) return array[0];
    if (n == 2) return max(array[0], array[1]);
    
    return max(maxSubsetSumNoAdjacent(vector<int>(array.begin(), array.end() - 1)), 
               maxSubsetSumNoAdjacent(vector<int>(array.begin(), array.end() - 2)) + array[n-1]);
}

Giải thích:

  • Nếu danh sách trống, ta trả về 0. Nếu danh sách chỉ có một phần tử, ta trả về giá trị của phần tử đó.
  • Nếu danh sách có hai phần tử, ta trả về giá trị lớn hơn trong hai phần tử đó.
  • Nếu danh sách có ba phần tử trở lên, ta tính toán tổng lớn nhất có thể đạt được với các phần tử từ đầu đến phần tử thứ N-1 bằng cách sử dụng đệ quy và trả về giá trị lớn hơn trong hai kết quả sau đây:
    • Tổng lớn nhất có thể đạt được với các phần tử từ đầu đến phần tử thứ N-2.
    • Tổng lớn nhất có thể đạt được với các phần tử từ đầu đến phần tử thứ N-3 cộng với phần tử thứ N-1.
  • Chú ý rằng ta cần sử dụng một vector tạm để đưa các phần tử của mảng ban đầu vào đệ quy.

Cài đặt Thuật toán Tham lam với Python

def maxSubsetSumNoAdjacent(array):
    if not array:
        return 0
    if len(array) == 1:
        return array[0]
    if len(array) == 2:
        return max(array[0], array[1])
    
    second_last = max(array[0], array[1])
    last = max(array[0], array[1], array[2])
    
    for i in range(3, len(array)):
        curr = max(second_last + array[i], last)
        second_last = last
        last = curr
        
    return last

Giải thích:

  • Nếu danh sách trống, ta trả về 0. Nếu danh sách chỉ có một phần tử, ta trả về giá trị của phần tử đó.
  • Nếu danh sách có hai phần tử, ta trả về giá trị lớn hơn trong hai phần tử đó.
  • Nếu danh sách có ba phần tử trở lên, ta sử dụng hai biến second_last và last để lưu trữ tổng lớn nhất có thể đạt được với các phần tử từ đầu đến phần tử thứ i-2 và i-1, tương ứng. Với mỗi phần tử mới, ta tính toán tổng lớn nhất có thể đạt được bằng cách so sánh tổng lớn nhất có thể đạt được với các phần tử từ đầu đến phần tử thứ i-2 cộng với phần tử thứ i và tổng lớn nhất có thể đạt được với các phần tử từ đầu đến phần tử thứ i-1. Sau đó, ta cập nhật giá trị của second_last và last để chuẩn bị cho vòng lặp tiếp theo.
  • Cuối cùng, ta trả về giá trị của last.

Cài đặt Thuật toán Tham lam với C++

#include <bits/stdc++.h>
using namespace std;

int maxSubsetSumNoAdjacent(vector<int> array) {
    if (array.empty()) {
        return 0;
    }
    if (array.size() == 1) {
        return array[0];
    }
    if (array.size() == 2) {
        return max(array[0], array[1]);
    }
    
    int second_last = max(array[0], array[1]);
    int last = max(array[0], array[1], array[2]);
    
    for (int i = 3; i < array.size(); i++) {
        int curr = max(second_last + array[i], last);
        second_last = last;
        last = curr;
    }
    
    return last;
}

int main() {
    vector<int> array = {4, 3, 5, 200, 5, 3};
    int maxSum = maxSubsetSumNoAdjacent(array);
    cout << maxSum << endl; // 207
    return 0;
}

Giải thích:

  • Nếu danh sách trống, ta trả về 0. Nếu danh sách chỉ có một phần tử, ta trả về giá trị của phần tử đó.
  • Nếu danh sách có hai phần tử, ta trả về giá trị lớn hơn trong hai phần tử đó.
  • Nếu danh sách có ba phần tử trở lên, ta sử dụng hai biến second_last và last để lưu trữ tổng lớn nhất có thể đạt được với các phần tử từ đầu đến phần tử thứ i-2 và i-1, tương ứng. Với mỗi phần tử mới, ta tính toán tổng lớn nhất có thể đạt được bằng cách so sánh tổng lớn nhất có thể đạt được với các phần tử từ đầu đến phần tử thứ i-2 cộng với phần tử thứ i và tổng lớn nhất có thể đạt được với các phần tử từ đầu đến phần tử thứ i-1. Sau đó, ta cập nhật giá trị của second_last và last để chuẩn bị cho vòng lặp tiếp theo.
  • Cuối cùng, ta trả về giá trị của last.

Kết luận

Trên đây là những thuật toán phổ biến để giải quyết bài toán Maximum Sum of Non-adjacent Elements, bao gồm thuật toán Đệ quy, Quy hoạch động và Tham lam. Mỗi thuật toán có ưu điểm và hạn chế riêng, và sẽ phù hợp hơn tùy thuộc vào đầu vào của bài toán.

Thuật toán Đệ quy có cách tiếp cận trực quan, dễ hiểu, tuy nhiên độ phức tạp tính toán của thuật toán này là O(2^n), khiến cho nó không phù hợp để xử lý những đầu vào lớn.

Thuật toán Quy hoạch động giải quyết bài toán bằng cách tính toán và lưu trữ các giá trị trung gian, từ đó giảm thiểu độ phức tạp tính toán và tối ưu hóa hiệu quả của thuật toán. Tuy nhiên, việc lưu trữ các giá trị trung gian có thể tiêu tốn nhiều bộ nhớ, đặc biệt là khi xử lý đầu vào lớn.

Thuật toán Tham lam cũng là một cách tiếp cận tối ưu hóa hiệu quả, tuy nhiên nó chỉ đưa ra giải pháp tốt nhất đến thời điểm đó mà không đảm bảo rằng nó sẽ là giải pháp tốt nhất cho toàn bộ bài toán. Nếu bài toán có nhiều điều kiện hơn và có nhiều hơn hai phương án để chọn, thuật toán Tham lam có thể không đưa ra kết quả chính xác.

Tóm lại, để giải quyết bài toán Maximum Sum of Non-adjacent Elements, chúng ta có nhiều cách tiếp cận khác nhau. Việc chọn thuật toán nào sẽ phụ thuộc vào độ phức tạp của bài toán, kích thước đầu vào, yêu cầu về thời gian và bộ nhớ, và nhiều yếu tố khác nữa./.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *