[0xc0der]

I have been recently thinking about the NP-complete class of problems particularly the knapsack problem (it is easy to understand and attack). And I think it is really solvable in polynomial time. I actually tried and posted my solution here. https://news.ycombinator.com/item?id=41341608 a bit of feedback would be really helpful.

[mbmjertan]

Your solution is not an exact solution to the knapsack problem, but a (relatively well known) greedy heuristic approach towards the problem. It is a good approach towards a solution, but the knapsack problem isn’t as trivial as it seems.

For a counterexample, imagine you have a ton of items that have a weight of 10^-20 and value of 1, and a single item that has the weight of whatever is the capacity of the knapsack (so it’s only thing that fits if it’s inserted to the knapsack) and the value of +infinity.

All items have their cost ≈ 0, so whether you fit all of the “light but valueless” items or the single “heavy but extremely valuable” item depends on how you sort when costs are equal.

An improved heuristic would take the value into account more than just having it as a factor, but it’s not easy to design.

I would recommend finding an open course on algorithm design and analysis and going through the lessons while trying to extrapolate approaches to problems instead of just solutions to them.

[0xc0der]

> Your solution is not an exact solution to the knapsack problem, but a (relatively well known) greedy heuristic approach towards the problem.

can point me to where to find more about this.

> For a counterexample, imagine you have a ton of items that have a weight of 10^-20 and value of 1, and a single item that has the weight of whatever is the capacity of the knapsack (so it’s only thing that fits if it’s inserted to the knapsack) and the value of +infinity.

that is rather an extreme example. i do not see the how it affects the validity of the solution in most cases.

> I would recommend finding an open course on algorithm design and analysis and going through the lessons while trying to extrapolate approaches to problems instead of just solutions to them.

implementing solutions is the concrete result of extrapolating approaches and choosing the best one to implement. and that is the pragmatic approach.

[mbmjertan]

> can point me to where to find more about this

Sorry, I’m not too familiar with English-language literature on algorithm design. I just remember this from my uni course on it :)

I believe we used Introduction to Algorithms by Cormen et al. as the basis, so it should be covered in depth there - but I’m not too sure.

> that is rather an extreme example. i do not see the how it affects the validity of the solution in most cases.

This is a fair point, but also a distinguishing factor between a heuristic and exact approach to algorithm solutions to problems. Algorithmic solutions usually have theorem proof-level rigor for exactness. Also, I just used the easiest counterexample to come up with :)