> 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.
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 :)
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.