vib_1's blog

Unbounded knapsack with condition that number of items taken be has to be a fibonacci number
By vib_1, history, 6 years ago, In English

How to solve the following question

You are given two integer arrays of size N, W(weight) and V(values), an infinite quantity of any item is available, You have to maximize the sum of values such that total weight is less than or equal to capacity C and the total number of items taken is a Fibonacci number

1 <= N <= 1000
1 <= C <= 1000
1 <= W(i) <= 1000
1 <= V(i) <= 1000

P.S. This was an interview question

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

Comments Comments (3)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please specify the source and restriction of the problem.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please elaborate the problem. I'm unable to understand the question being asked.

→ Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

The dp-solution would be

  • $$$dp[k][j] =$$$ best result if $$$k$$$ elements ($$$0\leq k\leq C$$$) are taken and $$$j$$$ weight units are used ($$$0\leq j\leq C$$$)
  • it can simply calculated by three for loops
  • initialize $$$dp$$$ by $$$-\infty$$$
  • initialize $$$dp[0][0]=0$$$
  • calculate values bottom up by formula $$$dp[k][j]=\max\limits_{i=1,\ldots,N}\lbrace dp[k-1][j-W(i)]+V(i)\rbrace$$$
  • take maximum result among those values $$$dp[k][j]$$$, where $$$k$$$ is a Fibonacci number
  • complexity: $$${\mathcal{O}}(C^2\cdot N)$$$
  • Maybe you can reduce one factor $$$C$$$ or $$$N$$$ to $$$\log(C)$$$ or $$$\log(N)$$$ with elaborate data structure
→ Reply