I am trying to learn Dynamic programming. I came across: https://youtu.be/U4O3SwDamA4?t=1407 I know basics of DP although they are not yet intuitive for me. Now, he talks about
and finally 0/k knapsack
While i tried to search 0/k knapsack, I am getting optimised solution (O(nS)) and not the solution that is extracted from 0/1 directly and have complexity of O(nKS). Anyone having nay resource to share or having a good grasp for the same is welcomed :) Thank you
I think the "naïve" solution the presenter is briefly mentioning has runtime complexity O(KS), given the way he defined K to be the sum of all the item limits. The idea is to convert it into a 0/1 problem by making ki copies of each item type.
Assume you've got k0 items of type 0, k1 items of type 1, and so on (so those are the limits to how many items you may take of each type). K is the total number of items (the sum of all the ki). Now, if you take this collection of items and start considering every item to be distinct from all the others, you have a 0/1 problem! The first item of type 0 is now item 0 in our new problem, the second item of type 0 is item 1 in our new problem, the last item of type 0 is item k0 - 1 in our new problem - and they all have weight w0 and value v0. The first item of type 1 is item k0 in our new problem, and so on. So we can now solve this as a 0/1 knapsack problem, but it's got K items instead of n; thus, the complexity is O(KS). However, if you define K to be the average of all the ki, or if every item has the same limit K, the complexity is indeed O(nKS).