ในบทความนี้ เราจะอภิบายปัญหาการจัดเรียงอาร์เรย์ที่กำหนด n ตัวเลข เราต้องเลือกสมาชิกจากอาร์เรย์ สำหรับการเลือกแต่ละสมาชิก เราจะได้คะแนนที่คำนวณจาก ค่าของสมาชิกปัจจุบัน × จำนวนสมาชิกที่เลือกก่อนหน้านี้ คุณควรเลือกสมาชิกเพื่อให้ได้คะแนนสูงสุด เช่น:
Input : arr[] = { 3, 1, 5, 6, 3 }
ถ้าเลือกตามลำดับเดิม คะแนน = 3×0 + 1×1 + 5×2 + 6×3 + 3×4 = 41
เพื่อให้คะแนนสูงสุด ให้เลือกตามลำดับ { 1, 3, 3, 5, 6 }
คะแนน = 1×0 + 3×1 + 3×2 + 5×3 + 6×4 = 48 (สูงสุด)
Output : 48
Input : arr[] = { 2, 4, 7, 1, 8 }
Output : 63
แนวทางแก้ปัญหา
จากตัวอย่าง เราเห็นว่าเพื่อให้ได้คะแนนสูงสุด เราต้องเลือกสมาชิกจากน้อยไปมาก แนวทางคือ:
- เรียงลำดับอาร์เรย์จากน้อยไปมาก (Ascending)
- เริ่มเลือกสมาชิกจาก index 0 ถึงสุดท้าย
- คำนวณคะแนนจากการเลือกแต่ละสมาชิก
ตัวอย่างโค้ด
#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]);
// เรียงลำดับอาร์เรย์
sort(arr, arr + n);
int points = 0;
// เดินผ่านอาร์เรย์และคำนวณคะแนน
for (int i = 0; i < n; i++) {
points += arr[i] * i;
}
cout << "Maximum points: " << points;
return 0;
}
ผลลัพธ์
Maximum points: 63
คำอธิบายโค้ด
โค้ด C++ นี้เข้าใจง่าย แรกเราเรียงอาร์เรย์ แล้ววนลูปด้วย for และคำนวณคะแนนจากการเลือกแต่ละสมาชิกจากต้นจนจบ
สรุป
ในบทความนี้ เราอภิบายปัญหาการเลือกสมาชิกในอาร์เรย์เพื่อให้ได้คะแนนสูงสุด โดยคะแนนคำนวณจาก i × arr[i] เราใช้ Greedy Approach คือเรียงจากน้อยไปมาก พร้อมโค้ด C++ สามารถเขียนในภาษาอื่นได้เช่น C, Java, Python หวังว่าจะเป็นประโยชน์
