I've encountered the following problem during two of my hiring challenges(on HackerEarth).The question is not available online, so here is the problem statement to the best of my memory:
Given a knapsack with M weight and n items, each with a positive weight w and positive value v(given as array weight[] and val[] ).Every item is available infinite times to be taken.But if you take a item x number of times, then all the other items(if taken) have to be taken x number of times.
Here x is a Fibonacci number less than 100.
Find the maximum value you can have while total weight of the knapsack is <= M.
constraints:
n <= 20
(M, weights, vals)<=1e9
Sample Test case:
n=2, M = 125
weight=[50, 25]
val =[100, 51]
for x=1: max val is 100+51 = 151
for x=2: max val is 2*100 = 200
for x=3: max val is 3*51 = 153
for x=5: max val is 5*51 = 255
for rest of the x: max val will be 0
Could anyone suggest how to approach it.
Here is what I did:
Generated all the possible subsets of items(using bitmasking) and for each subset, I kept on multiplying its weight with x = 1,2,3,5... until the weight exceeds M while keeping the count of max val obtained so far.After 2^n iterations, even though I had my answer, but it passed just the 3 out of 15 test cases and got TLEd for the rest.