Untitled
unknown
plain_text
5 months ago
841 B
2
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