Untitled

 avatar
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