{ "@context": "https://schema.org", "@type": "Organization", "name": "Brainscape", "url": "https://www.brainscape.com/", "logo": "https://www.brainscape.com/pks/images/cms/public-views/shared/Brainscape-logo-c4e172b280b4616f7fda.svg", "sameAs": [ "https://www.facebook.com/Brainscape", "https://x.com/brainscape", "https://www.linkedin.com/company/brainscape", "https://www.instagram.com/brainscape/", "https://www.tiktok.com/@brainscapeu", "https://www.pinterest.com/brainscape/", "https://www.youtube.com/@BrainscapeNY" ], "contactPoint": { "@type": "ContactPoint", "telephone": "(929) 334-4005", "contactType": "customer service", "availableLanguage": ["English"] }, "founder": { "@type": "Person", "name": "Andrew Cohen" }, "description": "Brainscape’s spaced repetition system is proven to DOUBLE learning results! Find, make, and study flashcards online or in our mobile app. Serious learners only.", "address": { "@type": "PostalAddress", "streetAddress": "159 W 25th St, Ste 517", "addressLocality": "New York", "addressRegion": "NY", "postalCode": "10001", "addressCountry": "USA" } }

Knapsack Flashcards

(5 cards)

1
Q

What is the 0/1 Knapsack pattern and when is it used?

A

Solves optimization using dynamic programming for item selection.
Use Case: Maximize value within capacity.

Example: [No LeetCode match, course example: Knapsack].

Action: Verbalize use case aloud.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are the key steps for the 0/1 Knapsack?

A
  1. Create DP table for items and capacity.
  2. Fill table: max value including/excluding item.
  3. Return max value.

Action: Explain steps for Knapsack aloud.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

How does the 0/1 Knapsack apply to Knapsack?

A

Maximize value of items within weight limit.
Approach: Use DP to compute max value for each capacity.

Example: Knapsack. Action: Verbalize solution logic aloud.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What are the complexity and gotchas of the 0/1 Knapsack?

A

Time: O(nW), Space: O(nW).

Gotchas: Zero capacity, no items.

Action: List edge cases for Knapsack aloud.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Code example for the 0/1 Knapsack.

A

```python
from typing import List
def knapsack(values: List[int], weights: List[int], capacity: int) -> int:
n = len(values)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
if weights[i-1] <= w:
dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1])
else:
dp[i][w] = dp[i-1][w]
return dp[n][capacity]
~~~

How well did you know this?
1
Not at all
2
3
4
5
Perfectly