Cho tập số nguyên. Tìm số 'd' mà d = a + b + c, tối đa hóa (a+b+c), tất cả a,b,c,d trong tập. Tập ít nhất 1, tối đa 1000 phần tử. Tập {2, 3, 5, 7, 12}, d lớn nhất 12 = 2+3+7.
Dùng băm: lưu tổng mọi cặp (a+b) vào bảng băm, duyệt cặp (c,d) tìm (d-c) trong bảng. Nếu khớp, đảm bảo không trùng phần tử, không dùng hai lần cùng phần tử.
Ví dụ mã nguồn
#include<iostream> #include<unordered_map> #include<climits> using namespace std; int findElementsInSet(int arr[], int n) { unordered_map<int, pair<int, int> > table; for (int i = 0; i < n - 1; i++) for (int j = i + 1; j < n; j++) table[arr[i] + arr[j]] = { i, j }; int d = INT_MIN; for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { int abs_diff = abs(arr[i] - arr[j]); if (table.find(abs_diff) != table.end()) { pair<int, int> p = table[abs_diff]; if (p.first != i && p.first != j && p.second != i && p.second != j) d = max(d, max(arr[i], arr[j])); } } } return d; } int main() { int arr[] = { 2, 3, 5, 7, 12 }; int n = sizeof(arr) / sizeof(arr[0]); int res = findElementsInSet(arr, n); if (res == INT_MIN) cout << "Cannot find the value of d"; else cout << "Max value of d is " << res; } Kết quả
Max value of d is 12