🔰 Wikipedia
🐻 Youtube
Link01

2.1.6.1.1. What is 0/1 Knapsack Problem?

• Given a knapsack with maximum capacity $W$ , and a set $S$ consisting of $n$ items
• Each item $i$ has some weight $w_i$ and benefit value $b_i$(all $w_i$, $b_i$ and $W$ are integer values)
• Problem: How to pack the knapsack to achieve maximum total value of packed items?

2.1.6.1.2. Solution

• brute-force approach

  

• dynamic programming

  

2.1.6.1.3. Code

https://gist.github.com/BiruLyu/b7ef86cee3a17427dd4f24e064f9d271

2.1.6.1.4. Related Topics

Fractional Knapsack Problem