zarif_2002's blog

By zarif_2002, history, 10 months ago, In English,

when we are asked for solving knapsack problem where i-th item has exactly K_i copies then what to do without merging them into array.

for example, n = 2, V = {100, 30}, W = {17, 10}, K = {3,4}, S = 50. this means you can use item-1 3 times and item-2 4 times. then, i can merge the array as,

V = {100, 100, 100, 30, 30, 30, 30} and W = {17, 17, 17, 10, 10, 10, 10} and then using original knapsack. but that would take a lot of time--- O(S*sum of k).

how can i get a better solution.

 
 
 
 
  • Vote: I like it
  • -4
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

constraints?

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Make log(Ki) copies for each Ki. Like for every set bit of Ki at pth position, make a copy having value Vi × 2p and weight Wi × 2p. Then, time complexity will be O()