Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
504 B
2
Indexable
Never
#include <iostream>
#include <vector>

int numberOfProducts(int n, int x, std::vector<int>& arr) {
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(x + 1, 0));

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= x; ++j) {
            dp[i][j] = dp[i - 1][j];  // Initially, assume not buying the current product

            if (j >= arr[i - 1]) {
                dp[i][j] = std::max(dp[i][j], dp[i - 1][j - arr[i - 1]] + 1);
            }
        }
    }

    return dp[n][x];
}