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.
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(
)