คำชี้แจงปัญหา
จากอาร์เรย์ของตัวเลข N ภารกิจคือการหาผลรวมสูงสุดที่สามารถรับได้โดยการเพิ่มตัวเลขที่มีจำนวนชุดบิตเท่ากัน
ตัวอย่าง
หากอาร์เรย์อินพุตเป็น {2, 5, 8, 9, 10, 7} เอาต์พุตจะเป็น 14 −
-
จำนวนชุดบิตใน 2 คือ 1
-
จำนวนชุดบิตใน 5 คือ 2
-
จำนวนชุดบิตใน 8 คือ 1
-
จำนวนชุดบิตใน 9 คือ 2
-
จำนวนชุดบิตใน 10 คือ 2
-
จำนวนชุดบิตใน 7 คือ 3
แล้วผลรวมของ (5 + 9 + 10) คือ 24 ซึ่งจำนวนบิตเซ็ต =2
อัลกอริทึม
-
สำรวจในอาร์เรย์และนับจำนวนชุดบิตสำหรับทุกองค์ประกอบ
-
เริ่มต้นอาร์เรย์สำหรับ 32 บิต โดยสมมติว่าตัวเลขมีชุดบิตสูงสุด 32 ชุด
-
วนซ้ำในอาร์เรย์และเพิ่มองค์ประกอบอาร์เรย์ไปยังตำแหน่งที่ระบุจำนวนบิตที่ตั้งไว้
-
สำรวจและหายอดรวมแล้วส่งคืน
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int bitCount(int n){
int count = 0;
while (n) {
count++;
n = n & (n - 1);
}
return count;
}
int maxSum(int arr[], int n){
int bits[n];
for (int i = 0; i < n; i++) {
bits[i] = bitCount(arr[i]);
}
int sum[32] = { 0 };
for (int i = 0; i < n; i++) {
sum[bits[i]] += arr[i];
}
int maximum = 0;
for (int i = 0; i < 32; i++) {
maximum = max(sum[i], maximum);
}
return maximum;
}
int main(){
int arr[] = {2, 5, 8, 9, 10, 7};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum sum = " << maxSum(arr, n) << endl;
return 0;
} ผลลัพธ์
เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -
Maximum sum = 24
