Giả sử chúng ta có một mảng A với N phần tử. Có một số khác T. Hãy xem xét Amal đang cố gắng tham gia vào một cuộc thi lập trình. Nó kéo dài trong T phút và trình bày N vấn đề. Anh ấy có A [i] thời gian để giải quyết vấn đề thứ i. Anh ta sẽ chọn không hoặc nhiều vấn đề để giải quyết trong số N vấn đề, sao cho tổng cộng không mất T phút để giải chúng. Chúng tôi phải tìm ra khoảng thời gian dài nhất có thể để giải quyết vấn đề lựa chọn của anh ấy.
Vì vậy, nếu đầu vào là T =17; A =[2, 3, 5, 7, 11], thì kết quả sẽ là 17, bởi vì nếu anh ta chọn bốn bài toán đầu tiên, anh ta mất tổng cộng 2 + 3 + 5 + 7 =17 phút để giải chúng, mà là thời gian dài nhất có thể không quá T phút.
Các bước
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
n := size of A Define an array b of size (n / 2) and c of size (n - n/2) for initialize i := 0, when i < n / 2, update (increase i by 1), do: b[i] := A[i] for initialize i := n / 2, when i < n, update (increase i by 1), do: c[i - n / 2] = A[i] Define an array B, C for bit in range 0 to 2^(n/2), increase bit after each iteration, do p := 0 for initialize i := 0, when i < n / 2, update (increase i by 1), do: if bit AND 2^i is non zero, then p := p + b[i] insert p at the end of B for bit in range 0 to 2^(n - n/2), increase bit after each iteration p := 0 for initialize i := 0, when i < n - n / 2, update (increase i by 1), do: if bit AND 2^i is non-zero, then p := p + c[i] insert p at the end of C mx := 0 sort the array C for initialize i := 0, when i < size of B, update (increase i by 1), do: if t - B[i] < 0, then: Ignore following part, skip to the next iteration itr = next larger element of (t - B[i]) in C (decrease itr by 1) mx := maximum of mx and (itr + B[i]) return mx
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#include <bits/stdc++.h>
using namespace std;
int solve(int t, vector<int> A){
int n = A.size();
vector<int> b(n / 2), c(n - n / 2);
for (int i = 0; i < n / 2; i++)
b[i] = A[i];
for (int i = n / 2; i < n; i++)
c[i - n / 2] = A[i];
vector<int> B, C;
for (int bit = 0; bit < (1 << (n / 2)); bit++){
int p = 0;
for (int i = 0; i < n / 2; i++){
if (bit & (1 << i))
p += b[i];
}
B.push_back(p);
}
for (int bit = 0; bit < (1 << (n - n / 2)); bit++){
int p = 0;
for (int i = 0; i < n - n / 2; i++){
if (bit & (1 << i))
p += c[i];
}
C.push_back(p);
}
int mx = 0;
sort(C.begin(), C.end());
for (int i = 0; i < B.size(); i++){
if (t - B[i] < 0)
continue;
auto itr = upper_bound(C.begin(), C.end(), t - B[i]);
itr--;
mx = max(mx, *itr + B[i]);
}
return mx;
}
int main(){
int T = 17;
vector<int> A = { 2, 3, 5, 7, 11 };
cout << solve(T, A) << endl;
} Đầu vào
17, { 2, 3, 5, 7, 11 } Đầu ra
17