Hacker News new | past | comments | ask | show | jobs | submit login

It is effectively finite in that the knapsack has a finite capacity and there is a finite selection of items with positive weight, hence the number of items that can fit into the knapsack is limited by the knapsack capacity divided by the smallest item weight. So, while for the unbounded knapsack problem the number of instances of an item that may be included is not limited, it is effectively still limited by the knapsack capacity. Therefore the number of item combinations that have to be considered is finite as well.

The GP had put "solvable" in quotes. I understood the GP to say that for space planning, there may not be an algorithm that is guaranteed to produce an answer in finite time. For the knapsack problem there is such an algorithm (even if that finite time, due to NP-completeness, could be very long).

The formal term "solvable", as applied to decision problems, actually only means "semidecidable", a much weaker property, see https://en.wikipedia.org/wiki/Decision_problem#Decidability.




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: