Trong bài viết này, ta sẽ thảo luận bài toán sắp xếp lại mảng cho trước gồm n số. Cơ bản, ta phải chọn các phần tử từ mảng. Với việc chọn mỗi phần tử, ta nhận được một số điểm được đánh giá bằng giá trị phần tử hiện tại * số phần tử đã chọn trước phần tử hiện tại. Bạn nên chọn các phần tử để đạt điểm tối đa. Ví dụ −
Input : arr[ ] = { 3, 1, 5, 6, 3 } Nếu ta chọn phần tử theo cách cho trước, điểm sẽ là = 3 * 0 + 1 * 1 + 5 * 2 + 6 * 3 + 3 * 4 = 41 Để tối đa hóa điểm ta phải chọn phần tử theo thứ tự { 1, 3, 3, 5, 6 } = 1 * 0 + 3 * 1 + 3 * 2 + 5 * 3 + 6 * 4 = 48(tối đa) Output : 48 Input : arr[ ] = { 2, 4, 7, 1, 8 } Output : 63Phương pháp tìm giải pháp
Nhìn ví dụ, ta thấy để đạt điểm tối đa, ta cần chọn phần tử từ nhỏ đến lớn. Phương pháp tìm giải pháp là:
- Sắp xếp mảng cho trước theo thứ tự tăng dần.
- Bắt đầu chọn phần tử từ chỉ số 0 đến cuối.
- Tính điểm nhận được từ việc chọn mỗi phần tử.
Ví dụ
#include <bits/stdc++.h> #include <iostream> using namespace std; int main () { int arr[] = { 2, 4, 7, 1, 8 }; int n = sizeof (arr) / sizeof (arr[0]); // sắp xếp mảng sort (arr, arr + n); int points = 0; // duyệt mảng và tính điểm for (int i = 0; i < n; i++) { points += arr[i] * i; } cout << "Maximum points: " << points; return 0; }Kết quả
Maximum points: 63
Giải thích mã trên
Mã C++ này dễ hiểu. Đầu tiên ta sắp xếp mảng rồi duyệt mảng dùng vòng lặp for và tính điểm đạt được bằng cách chọn mỗi phần tử từ đầu đến cuối.
Kết luận
Trong bài viết này, ta thảo luận bài toán chọn phần tử trong mảng theo thứ tự để đạt điểm tối đa với điểm tính bằng i * arr[i]. Ta áp dụng tham lam để giải bài toán và đạt điểm tối đa. Cũng thảo luận mã C++ làm tương tự, ta có thể viết mã này bằng bất kỳ ngôn ngữ nào khác như C, Java, Python, v.v. Hy vọng bạn thấy bài viết hữu ích.