Блог пользователя vib_1

Unbounded knapsack with condition that number of items taken be has to be a fibonacci number
Автор vib_1, история, 6 лет назад, По-английски

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

  • Проголосовать: нравится
  • -14
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please specify the source and restriction of the problem.

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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
→ Ответить