i want to know how to optimize classic 0/1 knapsack to 0/k knapsack . the problem link is https://open.kattis.com/problems/thief
# | User | Rating |
---|---|---|
1 | ecnerwala | 3649 |
2 | Benq | 3581 |
3 | jiangly | 3578 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | tourist | 3565 |
8 | maroonrk | 3531 |
9 | Radewoosh | 3521 |
10 | Um_nik | 3482 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
3 | adamant | 161 |
4 | TheScrasse | 159 |
5 | nor | 158 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 152 |
8 | SecondThread | 146 |
8 | orz | 146 |
10 | pajenegod | 145 |
i want to know how to optimize classic 0/1 knapsack to 0/k knapsack . the problem link is https://open.kattis.com/problems/thief
Name |
---|
a naive solution would involve storing k, and looping k times on an item during the knapsack this does not work for cases where k is large
however, 0/k knapsack can be transformed into 0/1 knapsack, by making big items which are 2^X items combined together, since binary can be used to form any number up to a point
i have adapted a paragraph from singapore's national olympiad in informatics preliminary round writeup
Notice that we can group the K copies into O(log K) groups where the sizes are powers of 2 except the last one. For example, if K = 25, we can group into 5 groups of size 1, 2, 4, 8, 10 respectively. Notice that the size of the groups add up to 25 and also any number from 1 to 25 can be represented by a sum of some subset of the above groups. Thus, by considering subsets of these groups, we would have considered every possibility of taking 1, 2, 3 ..., K items.
this makes it efficient as there are log k items instead of k of them
after this, normal knapsack can be applied on the new items formed
still this solution not work it exceed time limit . we can do this in O(knapsack_size*num_of_items) i am getting how to do this so can any body help me ??
This question isn't asking for 0/k knapsack where up to k items are taken
As I replied before you deleted my reply, you can use bottom up DP such as the one found on geeksforgeeks where values are calculated for all knapsack sizes
I don't think that this question simply asks for 0/k knapsack (or bounded knapsack, the popular name). You can check here and here for a better explanation.
can any explain how to do this problem