* http://en.wikipedia.org/wiki/Knapsack_problem - The knapsack problem with each type of item j having a distinct value per unit of weight (vj = pj/wj) is considered one of the easiest NP-complete problems. Indeed empirical complexity is of the order of O((log n)2) and very large problems can be solved very quickly, e.g. in 2003 the average time required to solve instances with n = 10,000 was below 14 milliseconds using commodity personal computers[1]. However in the degenerate case of multiple items sharing the same value vj it becomes much more difficult with the extreme case where vj = constant being the subset sum problem with a complexity of O(2N/2N).
The multidimensional problem is usually reduced to a one-dimensional one by use of Lagrangian Multipliers that, however, do not generally yield the exact solution to the problem posed. Here some new algorithms are developed that are applied within a dynamic programming framework. Additionally, the methods make integral use of an interactive computer system in which the heuristics of the problem solver are applied and changed as the character of the solution process evolves.
Greedy Algorithm - keep taking most valuable items until maximum weight is reached Not-So-Greedy Algorithm - Greedy Algorithm, then throw out heaviest item, continue Greedy Algorithm
... Not-So-Greedy Algorithm seemed to result in a bit better sums
* http://en.pudn.com/downloads10/doc/detail37427_en.html - C++ keeles. ... five small programs, namely : 0-2-1 knapsack problem, the binary tree traversal and the chain table and that the realization of the maze path, the optimal resource allocation algorithm. Every procedure is described in detail in, I was doing it two semesters of part of the experiment.
* TODO: minu enda ligikaudse kuid enamasti (?) täpse 0-1 knapsack lahendaja kood, mis töötab lineaarse ajaga (tööaeg sõltub ligikaudu lineaarselt muutujate arvust) ka "degenerate" juhtumitel(ehk "subset sum problem" korral) ning on ka sõbraliku mälukasutusega
