2
$\begingroup$

Suppose I need exactly $X$ flowerpots.

I have $Y$ flowerpots to choose from, and $Y > X$.

Each of the $Y$ flowerpots has a cost and a capacity. I have a fixed budget to buy flowerpots. The budget, and costs and capacity of each flowerpot are all strictly positive integers. Assume that the total cost of the cheapest $X$ flowerpots do not exceed my budget.

My goal is to maximize total capacity subject to not exceeding my budget (I can spend less, but not more).

If I didn't need exactly $X$ flowerpots, this is the standard 0/1 knapsack problem. However, I need exactly $X$ flowerpots.

What does this problem become, and what algorithm can I use to solve this?

$\endgroup$
  • $\begingroup$ What did you try, where did you get stuck? It is not hard to modify the dynamic programming approach to the Knapsack to solve this problem, for example. $\endgroup$ – Marcus Ritt Jul 9 at 4:01
  • $\begingroup$ Have you seen this question? cs.stackexchange.com/questions/18492/… $\endgroup$ – phan801 Jul 9 at 12:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.