Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

From the very section of the article you quoted: "In computer science, a problem that can be broken apart like this is said to have optimal substructure." - There is no reason whatsoever that any problem could be broken down to this. In fact there are many problems for which it is known to be impossible. The article on optimal substructure lists a few.


Yes. The principle of suboptimality only applies to problems which are optimally solved by dynamic programming. This is a small subset of problems and the knapsack problem is not one of those problems solved by dynamic programming. It does not have optimal substructure.




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

Search: