Untitled
unknown
plain_text
a year ago
841 B
4
Indexable
int find_max_elements(vector<int> array) {
int n = array.size();
int target = array[0]; // Assuming the first element is the target
// Create a 2D DP table
vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));
// Base cases
dp[0][0] = true; // 0 elements can sum up to 0
// Fill the DP table
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= target; j++) {
dp[i][j] = dp[i - 1][j]; // Exclude the current element
if (j >= array[i - 1]) {
dp[i][j] |= dp[i - 1][j - array[i - 1]]; // Include the current element
}
}
}
// Find the maximum number of elements
int maxElements = 0;
for (int i = 1; i <= n; i++) {
if (dp[i][target]) {
maxElements = i;
}
}
return maxElements;
}
Editor is loading...
Leave a Comment