Number of ways I can have as least M itens chosen from L itens (L >= M), where the price of all chosen S itens can't be greater than Q

L = number of given itens 0 < L < 31

P[j] = price of item j

M = smaller quantity of items I must have

Q = Greater quantity which can be spent

Also, I can't have more than one item of each type.

Each test case of the problem is something like this:

L

P[0] P[1] ... P[L-1]

M

Q

Time Limit is 1s

I tried solving the problem with a modified knapsack solution, but it couldn't pass the expected time. I will show a part of the code I made:

int dp[31][31][10000];
int P[31];
bool used[31];

int knapsack(int pos, int sumOfItems, int qttItems) {
    if (dp[pos][qttItems][sumOfItems] != -1) return dp[pos][qttItems][sumOfItems];
    if(pos == L)
        return qttItems >= M ? 1 : 0; 
    if(L - pos + qttItems < M) return 0;
    if(((sumOfItems + P[pos] > Q) || (sumOfItems >= Q)) && (qttItems < M)) return 0;
    int solWithItem = 0;
    if((sumOfItems + P[pos] <= Q) && !used[pos]) {
        int newSum = sumOfItems + P[pos];
        used[pos] = true;
        solWithItem = knapsack(pos + 1, newSum, qttItems + 1);
        used[pos] = false;
    }
    int solWithoutItem = knapsack(pos + 1, sumOfItems, qttItems);
    return dp[pos][qttItems][sumOfItems] = solWithItem + solWithoutItem;
}
.
.
.
R = knapsack(0, 0, 0);

Algorithm

This approaches uses a basic divide and conquer strategy combined with a variation of the meet in the middle algorithm to reduce complexity and achieve good performance.

The divide and conquer strategy subdivides the problem at two-levels:

• Split L into left and right roughly equal sets
• Find the the costs for each permutation of 0 to M items in each set

This results in M+1 left and M+1 right sets of costs, which are sorted. These costs can be efficiently recombined using a variation of the meet in the middle algorithm computing the number of results that are <= Q in the process. Only matching sets such that the number of selected items totals M need to be paired which results in M+1 pairings.

The worst case performance for selecting 15 items from 31 is around 2ms on an M1 Ultra.

Sample Code

#include "core/util/tool.h"

/// Return the lexicographically next bit permutation with the same
/// number of bits set as `r`.
template<std::unsigned_integral T>
auto next_permutation_n(T n) {
    auto m = n bitor (n - 1);
    return (m + 1) bitor (((~m bitand -~m) - 1) >> (std::countr_zero(n) + 1));
}

/// Return the number of distinct subsets of size `k` given a set of
/// size `n` (informally, n choose k).
template<std::integral T, std::integral U>
auto n_choose_k(T n, U k) {
    if (k == 0) return T{1};
    if (k > n / 2) k = n - k;

    T r{1};
    for (auto i = 1; i <= k; ++i) {
        r *= n - i + 1;
        r /= i;
    }
    return r;
}

using BitMask = uint32_t; // Since the upper limit of nitems was specified as 32.
using Prices = std::vector<int>;
using Costs = std::vector<int>;

auto cost_for_selected(const std::vector<int>& prices, BitMask selected) {
    int sum{};
    int idx{std::countr_zero(selected)};
    while (selected) {
        sum += prices[idx];
        selected >>= std::countr_zero(selected) + 1;
        idx += std::countr_zero(selected) + 1;
    }
    return sum;
}

struct Partition {
    Partition(const Prices& prices, int needed) {
        BitMask end_mask = BitMask{1} << prices.size();
        BitMask mask = (BitMask{1} << needed) - 1;
        while (mask < end_mask) {
            costs.push_back(cost_for_selected(prices, mask));
            mask = next_permutation_n(mask);
        }
        std::sort(costs.begin(), costs.end());
    }
    Costs costs;
};

int tool_main(int argc, const char *argv[]) {
    ArgParse opts
        (
         argValue<'m'>("needed", 10, "Items needed"),
         argValue<'q'>("cost", 20, "Maximum cost"),
         argValues<'*', std::vector, int>("prices", "Prices"),
         argFlag<'v'>("verbose", "Verbose diagnostics")
         );
    opts.parse(argc, argv);
    auto needed = opts.get<'m'>();
    auto cost = opts.get<'q'>();
    auto prices = opts.get<'*'>();
    auto nitems = prices.size();
    auto verbose = opts.get<'v'>();

    std::sort(prices.begin(), prices.end(), std::greater{});
    if (verbose) {
        cout << fmt::format("Items   : {}", nitems) << endl;
        cout << fmt::format("Needed  : {}", needed) << endl;
        cout << fmt::format("Cost    : {}", cost) << endl;
        cout << fmt::format("Prices  : ");
        for (auto price : prices)
            cout << price << ",";
        cout << endl;
    }

    if (nitems < needed)
        throw core::runtime_error("Need {} items, but only {} available", needed, nitems);
    if (nitems > 32)
        throw core::runtime_error("Maximum of 32 items, but {} available", nitems);

    // Partition the available items into left and right halfs (roughly).
    auto nleft = nitems / 2, nright = nitems - nleft;

    // Partition the prices into left and right.
    Prices left_prices, right_prices;
    for (auto i = 0; i < nleft; ++i)
        left_prices.push_back(prices[i]);
    for (auto i = 0; i < nright; ++i)
        right_prices.push_back(prices[i + nleft]);

    // Compute all the partitions, from 0 to needed for both left and right.
    std::vector<Partition> left, right;
    for (auto i = 0; i <= needed; ++i) {
        left.emplace_back(left_prices, i);
        right.emplace_back(right_prices, i);
    }

    // Combine partitions and count results.
    size_t n{};
    for (auto i = 0; i <= needed; ++i) {
        auto& left_costs = left[i].costs;
        auto& right_costs = right[needed - i].costs;

        if (left_costs.size() > right_costs.size())
            std::swap(left_costs, right_costs);

        for (int i = 0, j = right_costs.size() - 1; i < left_costs.size() and j >= 0; ++i) {
            auto lc = left_costs[i];
            while (j >= 0 and lc + right_costs[j] > cost)
                --j;
            if (j >= 0)
                n += j + 1;
        }
    }

    cout << fmt::format("result  : {}", n) << endl;

    return 0;
}