0/1 Knapsack Problem Using Dynamic Programming - Tutorial & Source Code
01 Knapsack Problem defined and explained. In this tutorial we explain why a greedy rule does not work and present a dynamic programming algorithm that fills out a table. The running time complexity of the dynamic programming algorithm is pseudo-polynomial, not quadratic, even though the table is two dimensional. Understanding the running time complexity gives a sense of why this problem is hard and why it's called "weakly NP-complete".
Source code of minimal implementation in JavaScript:
https://bitbucket.org/StableSort/play...
Source code implementation in Java:
https://bitbucket.org/StableSort/play...
Wikipedia: https://en.wikipedia.org/wiki/Knapsac...
Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.
Weak NP-completeness: https://en.wikipedia.org/wiki/Weak_NP...
This is a common problem that is given during coding interviews in engineering firms such as Google and Microsoft.
Written and narrated by Andre Violentyev
На этой странице сайта вы можете посмотреть видео онлайн 0/1 Knapsack Problem Using Dynamic Programming - Tutorial & Source Code длительностью часов минут секунд в хорошем качестве, которое загрузил пользователь Stable Sort 09 Декабрь 2019, поделитесь ссылкой с друзьями и знакомыми, на youtube это видео уже посмотрели 14,446 раз и оно понравилось 511 зрителям. Приятного просмотра!
