Understanding Dynamic Programming for Knapsack Problem and Solutions
Dynamic Programming is a powerful technique used to optimize solutions in the Knapsack Problem by selecting items with maximum value within certain constraints. This approach involves creating a table, making optimal choices, and outputting the best solution. The process is exemplified through a step-by-step illustration, showcasing the selection of items for a knapsack with limited capacity to maximize the total value. Longest Common Subsequence and Maximum Independent Set on Trees are also discussed, emphasizing the importance of efficient algorithms in solving complex problems.
- Dynamic Programming
- Knapsack Problem
- Optimal Solution
- Table Representation
- Longest Common Subsequence
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.
E N D
Presentation Transcript
Outline Knapsack revisited: How to output the optimal solution, and how to prove correctness? Longest Common Subsequence Maximum Independent Set on Trees.
Example 2 Knapsack Problem There is a knapsack that can hold items of total weight at most W. There are now n items with weights w1,w2, , wn. Each item also has a value v1,v2, ,vn. Goal: Select some items to put into knapsack 1. Total weight is at most W. 2. Total value is as large as possible. Output: the set of items to put into the Knapsack
Recall: States and Transition function Example: Capacity W = 4, 3 items with (weight, value) = (1, 2), (2, 3), (3, 4). States (sub-problems): What is the maximum value for a Knapsack with capacity j (= 0, 1, 2, 3, 4) and the first i (= 0, 1, 2, 3) items? Use a[i, j] to denote this maximum value, we have a[i - 1, j - wi] + vi (item i in knapsack) max a[i, j] = a[i - 1, j] (item i not in knapsack)
Dynamic Programming Table Example: Capacity W = 4, 3 items with (weight, value) = (1, 2), (2, 3), (3, 4). 0 1 2 3 4 0 0 0 0 0 0 1 0 2 2 2 2 2 0 2 3 5 5 +4 3 0 2 3 5 6
Outputting the Solution Remember the choice (arrows) in the DP table. 0 1 2 3 4 0 0 0 0 0 0 1 0 2 2 2 2 2 0 2 3 5 5 3 0 2 3 5 6 Solution = {1, 3}, value = 6
Outputting the Solution Another Example (capacity = 3) 0 1 2 3 4 0 0 0 0 0 0 1 0 2 2 2 2 2 0 2 3 5 5 3 0 2 3 5 6 Solution = {1, 2}, value = 5
Pseudo-code Knapsack 1. Initialize a[i, 0] = 0, a[0, j] = 0 (Base Case) 2. FOR i = 1 to n (Enumerate #items) 3. FOR j = 1 to W (Enumerate capacity) 4. a[i, j] = a[i-1, j] (Case 1: not using item i) 5. IF j >= w[i] and a[i-1, j-w[i]] + v[i] > a[i,j] (if Case 2 is better) 6. a[i, j] = a[i-1, j-w[i]] + v[i] (Case 2: using item i) Output(n, W) 1. IF n = 0 or W = 0 THEN RETURN 2. IF a[n, W] = a[n-1, W] THEN (Case 1) 3. Output(n-1, W) 4. ELSE (Case 2) 5. Output(n-1, W-w[n]) 6. Print(n)
Longest Common Subsequence Input: two strings a[] = ababcde and b[] = abbecd Subsequence: same definition as in LIS (can skip characters) E.g. abac is a subsequence of a[], but not b[] abed is a subsequence of b[] but not a[] Goal: Find the length of the longest common subsequence (LCS) In this example: LCS = abbcd , length = 5.
Max Independent Set on Trees Input: a tree Independent Set: Set of nodes that are not connected by any edges Goal: Find an independent set of maximum size.
Max Independent Set on Trees Input: a tree Independent Set: Set of nodes that are not connected by any edges Goal: Find an independent set of maximum size.
