0/1 Knapsack Problem by Dynamic Programming: Optimal Solutions for Maximizing Value

Solving the 0/1 Knapsack Problem involves finding the most optimal combination of items to maximize value while staying within a given weight limit. Dynamic Programming (DP) offers a three-step approach to address this optimization challenge efficiently. By calculating the Optimum function and following the recursive formula, DP efficiently determines the best-value configuration. Bottom-up and top-down table filling techniques further illustrate how to solve this problem effectively, showcasing different strategies for approaching the same issue.

• Knapsack Problem
• Dynamic Programming
• Maximizing Value
• Optimization
• DP

zjerm Follow

Uploaded on Sep 19, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. 0/1 Knapsack Problem by Dynamic Programming J.-S. Roger Jang ( ) MIR Lab, CSIE Dept. National Taiwan University jang@mirlab.org, http://mirlab.org/jang 2024/9/19

2. 0/1 Knapsack Problem by DP Given n objects, each with weight wiand value vi, . Find a combination of objects such that the total value is maximize and the total weights is within a given upper bound. DP three steps Optimum function D(i, j): max value when the first i items are considered and the total weight is j Recurrent formula D(i, j) = max{D(i-1, j), D(i-1, j-w(i)+v(i)} D(i, j) = 0 whenever i<=0 or j<=0 Answer D(m, n) 2/11

3. Example 1: Bottom-up Table Filling URL: https://www.youtube.com/watch?v=8LusJS5-AGo Bottom-up approach to fill the table row by row Value Weight 0 1 2 3 4 5 6 7 1 1 0 1 1 1 1 1 1 1 4 3 0 1 1 4 5 5 5 5 5 4 0 1 1 4 5 6 6 9 7 5 0 1 1 4 5 7 8 9 3/11

4. Example 2: Bottom-up Table Filling URL: https://www.youtube.com/watch?v=nLmhmB6NzcM Bottom-up approach to fill the table row by row Value Weight 0 1 2 3 4 5 6 7 8 1 2 0 0 1 1 1 1 1 1 1 2 3 0 0 1 2 2 3 3 3 3 5 4 0 0 1 2 5 5 6 7 7 6 5 0 0 1 2 5 6 6 7 8 4/11

5. Example 3: Top-down Table Filling URL: https://www.youtube.com/watch?v=149WSzQ4E1g Top-down approach: Only the circles need to be computed Faster! Value Weight 0 1 2 3 4 5 6 7 8 2 2 0 0 2 2 2 2 2 2 2 4 2 0 0 4 4 6 6 6 6 6 6 4 0 0 4 4 6 10 10 10 12 9 5 0 0 4 4 6 10 10 13 13 5/11