Is this multiple constraints Knapsack variation?


December 2018


156 time


I have checked out the other questions (especially this one) but I don't think any of them really tackles my problem.

Let's say we have N number of Buckets (tagged with a number) each of them contains an finite and greater than 0 number of token M(i) (M can change between different buckets).

Each token has two properties x and y (you can think at them like real numbers). My problem is to find the configurations that satisfy:

1) Only one or zero element can be selected from each bucket.

2) each element selected in the final configuration must have x properties greater than an input value X.

3) the sum over all the element of the properties y in the final configuration must be greater or equal of an input value Y. However, removing any of the element in the final list must result in a sum strictly less than Y.

4) configuration with less element should be preferred

Now, it appears to me similar to the multiple constraint Knapsack problem, however, there are a couple of differences and I cannot really wrap my head around (mainly the buckets and condition 3).


Because, I don't want to reinvent the wheel.

Has my problem a name and an known solution?

If not, which one is the closest algorithm to start with? Am I missing something obvious to make my problem to fall back to the Knapsack one?


Ideally, I am looking for a c++ (library/example/analysis), but I am happy to get references in any programming languages.

0 answers