0
$\begingroup$

Given a set $S$, a value function $v(s)$ and a cost function $c(s)$ for all $s \in S$, and integers $B$ and $K$, the classic formulation of the Knapsack problem asks if there is a subset $S' \subseteq S$ in which $\sum_{s \in S'} v(s) \geq K$ and $\sum_{s \in S'} c(s) \leq B$.

Is there a variation/special case of the Knapsack problem where there is no $B$? I read through this question: Is there a name for the knapsack problem with no bound on knapsack capacity?, but the author assumes multiple knapsacks.

One way to formulate the problem where no capacity is given could be to ask for the cheapest subset $S'$ where $\sum_{s \in S'} v(s) \geq K$, but then I'm not sure if this is still considered a Knapsack.

$\endgroup$
4
  • $\begingroup$ Not sure if the problem has a name, but there is a standard relation between your "cheapest subset" problem and knapsack. One is the search problem and another is the decision problem, and the standard approach is to use binary search (in this case on $B$). $\endgroup$
    – Dmitry
    Mar 28, 2023 at 16:32
  • $\begingroup$ @Dmitry I agree. After some further research, I suspect the problem might be more in the category of integer programming since we do not have a capacity constriant. I will keep the answers section open untill I am sure. $\endgroup$ Mar 29, 2023 at 8:54
  • $\begingroup$ Is there a variation...? Yes, you have just defined one. What is your real question? $\endgroup$
    – D.W.
    Mar 29, 2023 at 23:58
  • $\begingroup$ @D.W. My question is if the variation can still be considered a knapsack problem, or if it is something else (if so, what is it, and how can I show it?). Every formulation of the knapsack problem I have come across has a some capacity/weight/cost contraint that cannot be exceeded, where my problem does not. $\endgroup$ Mar 30, 2023 at 9:30

1 Answer 1

1
$\begingroup$

Is there such a variation? Yes, you have defined one. Can it be considered as a knapsack problem? As far as I know, there is no formal definition of what counts as a "knapsack problem", so that's a matter of opinion and up to you.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.