An FPTAS for the Knapsack Problem

Textbooks:
Computational Complexity: A Modern Approach by S. Arora and B. Barak.
Algorithm Design by J. Kleinberg and E. Tardos.
Lecture slides by K. Wayne accompanying the latter textbook:
www.cs.princet...

[@JikeWimblik]

From partial reductions of the napsack problem to combinations of 2 items to sniff out more item variants of the problem with blocks in some parts of the bag as to find clues for your particular napsack problem

[@沈骁瑜]

It’s been enjoyable journey into the Complexity theory. Thank you Matthias

[@Th0rmator]

Very nice explanation, easy to follow.

[@nikonru3287]

Really nice course, I watched it with interest and joy.

[@MarcDinh]

Really easy to follow and clearly explained. Excellent videos!
A minor nitpick: I don't remember there is an example of a P problem, would be nice to know some of them. Also maybe discuss about complete problems for other classes of problems than NP. Maybe there are no complete problem for RP or maybe it is not known if it exists, just make some comments in this case.

[@97edut]

amazing proof! thank you!

[@fjdk6009]

I want to learn this kind of mathematics. Do I need to study basic subjects to start this course?

[@manuelaayo4199]

Thank you for your explanation !
Got a question. If you added another item of value 134 833, rounding it would still give you 200 000. On that case, how can you distinguish the 2 objects ?

[@compscilessons]

If they have different weights, they will still be different. If they have the same weight, we do not have to distinguish them. In the solution, you will either decide to pick both, only one of them, or none. If the solution only includes one of them, you are free to pick either one and the gurantee on the total value of the solution will hold whatever choice you make. Of course, you might as well select the more valuable of the two, which would be 134,833 in this case.

[@jasonzuang7718]

Awesome Video!