zarif_2002's blog

a variation of 0/1 knapsack.
By zarif_2002, history, 6 years 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

Comments Comments (1)
| Write comment?
»
6 years 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()

→ Reply