Twisted Knapsack Problem(unbounded with Fibonacci constraint)

Question

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.

So the only weights available are Fibonacci numbers? The way the Fibonacci constraint plays seems unclear. — Olivier Melançon
No, weights are given in the weight[ ] array.Fibonacci numbers(x ) decide the number of times an element can be taken.Let me explain a test case for better understanding, suppose for x=2; each selected item has to be taken twice, so possible selections can be (100,100), (51,51), out of which the first one has higher value, so 200 is the answer.Hope that clears. — 4vedi.aayush
I do not get it, this would mean the weight of 100 always wins: x=3, 3*100. Why you conclude it is 3*51? — Aldert
This is a variation of the classic Knapsack problem, where you have to maximize the value inside the knapsack of fixed total weight.In your example, if you take the object with weight 50 & val 100 three times(for x=3), the total weight inside the knapsack will become 3*50, which exceeds M(=125 here), the maximum allowable weight inside the knapsack. — 4vedi.aayush

Nj Rafi Nj Rafi · Accepted Answer · 2019-06-19T21:14:04

I think one small optimization would pass all test cases. Precalculate the nearest smaller Fibonacci number for x. Now after generating all subset sum , divide m by the sum . Find the nearest smaller Fibonacci number of ( m / sum). Multiply it by sum. So the overall time complexity is O(2^n).

Twisted Knapsack Problem(unbounded with Fibonacci constraint)

1 Answers