🎙 Free live masterclass · Sun, 29 Nov, 7:00 pm IST · Java Full Stack roadmap Register free →
Skills101
← Dynamic Programming Quiz: all 8 questions

Dynamic Programming Quiz · Question 7 of 8

In 0/1 knapsack (each item at most once) with a 1D dp array, the inner loop over capacity should go…

In 0/1 knapsack (each item at most once) with a 1D dp array, the inner loop over capacity should go…

  1. A.Upwards (small to large)
  2. B.Downwards (large to small)
  3. C.In random order
  4. D.It doesn't matter
Answer & explanation

Correct answer: Downwards (large to small)

Going downwards reads dp[s − x] from before this item was added, so each item is used at most once.

Can you get the rest right without peeking?

Take the timed Dynamic Programming Quiz quiz free. Pass it to earn XP and count towards your certificate.

Start the quiz →