EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 3 1 Dynamic Programming
1.1 Introduction
As we learned in the previous week, many tough problems can more easily be solved through divide-and-conquer by breaking the problem into independent sub-problems and then efficiently combining the solutions to each sub-problem. Unfortunately, not all problems can be solved so easily.
Copyright By PowCoder代写 加微信 powcoder
A common scenario we encounter is a problem where we have a set of choices we can make, and each choice reduces the problem differently. Our goal is to make the best series of choices to optimize some parameters — this could include minimizing the total cost of all choices or maximizing some profit or reward. But without testing all combinations of choices (the number of which is usually staggeringly high), how can we find the best solution?
One approach is to use dynamic programming. There are several identifiers of situations in which dynamic programming algorithms might provide an efficient means to solve optimization problems. One is the presence of an optimal substructure. This means that the optimal solution to a subproblem will guarantee us an optimal solution to the global problem. Another indication that dynamic programming might be useful is if the overall problem has overlapping subproblems. That is, if after making several different sets of decisions we arrive at the same point where we must solve the same set of subproblems, regardless of how we arrived there. By using dynamic programming, we can solve these subproblems exactly once, store our solutions, then reuse the solutions each time we need them. This idea of storing solutions to overlapping subproblems in some data structure (a memo) is called memoization, and is a key part of dynamic programming. By memoizing solutions to smaller problems and reusing them each time they come up, we can vastly improve the speed of an optimizing algorithm while maintaining its correctness.
1.2 0-1 Knapsack Problem
The 0-1 Knapsack Problem presents the following challenge.
Definition 1.1 (0-1 Knapsack problem). You are given two n-length arrays containing positive integer weights W = (w1,w2,…,wn) and values V = (v1,v2,…,vn) of n items (where the ith item has weight wi ∈ N and value vi ∈ N ),1 and a knapsack with weight capacity C ∈ N0.
You must pick a subset of items S ⊆ {1, 2, . . . , n} (there are no copies or fractional items), such that the total weight of the chosen items is less than or equal to the weight capacity: i∈S wi ≤ C. What is the maximum total value you can obtain from objects in your knapsack, i∈S vi?
Note that this problem displays the characteristics of having an optimal substructure and over- lapping subproblems. If you already have a certain number of objects in the knapsack and have a fixed remaining weight capacity and subset of objects to choose from, then maximizing the value of the remaining objects you add will maximize the total value in your knapsack. Furthermore, given a certain subset of remaining objects and a capacity, it doesn’t matter how else you filled your knapsack; the solution to the subproblem will be the same. Since there are multiple ways for you to get to the same remaining subset and remaining capacity, this is a subproblem that recurs when solving this problem, so it is useful to utilize a dynamic programming algorithm in this context.
1Here we use N = {1,2,…} to denote the set of natural numbers and N0 = {0,1,2…} the set of nonnegative integers.
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 3
In order to solve this, we define the subproblem K(i, C) to be the maximum value we can obtain by considering only the first i objects and a knapsack with weight capacity equal to C. There are three cases:
1. i = 0 or C = 0: In this case, clearly K(i, C) = 0 because there are either no items or no space in the knapsack.
2. wi > C: In this case, you cannot fit the ith item in the knapsack, so your set of items in the knapsack must consist only of the first i − 1 items. That is, K(i, C) = K(i − 1, C)
3. If neither of the above cases hold, then you can either have the ith in the knapsack, or not, and the maximum value will be the larger of the two values you get from these two options. In other words, K(i, C) = max{K(i − 1, C − wi) + vi, K(i − 1, C)}. The first option gives you the maximum value you get if you add the ith item to the knapsack, and the second gives you the maximum value if you don’t.
Note that if we just implement a recursive algorithm using the above observations, our runtime complexity will be O(2n), where n is the total number of items. This is very bad! However, we can improve things by noting that there are only n · C possible subproblems that can occur that need to be calculated because our list of items and total capacity always decreases. Because of this, we can simply store the value of every subproblem we solve in a look-up table and then look it up when we need it again. This technique, as mentioned before, is called memoization.
There are two approaches to implementing this technique:
1. Bottom-Up (Iterative): In this approach, we take advantage of the fact that the solution to the problem with i items only depends on solutions of the problem with i − 1 items. Unfortunately, we can not really place any restriction on the values w can take, so we simply consider every possible available weight for each iteration. The pseudocode for this approach is shown below:
Input: Integers n, C , arrays W, V , and memo table DP.
Output: The maximum total value of objects the Knapsack can hold
1: 2: 3: 4:
10: 11: 12:
functionKnapsack(n,C,W,V) DP[n][C] ← −1 fori=0:ndo
DP [i][0] = 0 forj=0:Cdo
DP [0][j] = 0
fori=1:ndo
for j = 1 : C do
if W[i] > j then
DP [i][j] = DP [i − 1][j]
▷ Initialize values in lookup-table to -1
DP [i][j] = max(DP [i − 1][j − W [i]] + V [i], DP [i − 1][j]) return DP [n][C]
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 3
2. Top-Down (Recursive) In this approach, we implement a recursive algorithm. Following the recurrence relation used to define the problem, we make function calls into the smaller subproblems and solve them recursively.
Input: Integers n, C , arrays W, V . Again, note the 1-based indexing. Output: The maximum total value of objects the Knapsack can hold
1: 2: 3: 4: 5:
functionKnapsack(n,C,W,V) if n=0orC=0then
if W [n] > C then
return Knapsack(n − 1, C, W, V )
return max(Knapsack(n−1,C −W[n],W,V)+V[n], Knapsack(n−1,C,W,V))
3. Top-Down (Memoization) In this approach, we again implement a recursive algorithm, but before we make any recursive calls, we check a look-up table to see if we have already calculated the desired subproblems. If so, we simply use our stored values. If not, we recurse into the smaller subproblem and then store its result in our lookup table for later use:
Input: Integers n, C, arrays W, V , and lookup-table DP with values initialized to -1. Again, note the 1-based indexing.
Output: The maximum total value of objects the Knapsack can hold
1: 2: 3: 4: 5:
functionKnapsack(n,C,W,V,DP) if n=0orC=0then
return 0 ifDP[n−1][C]=−1then
DP [n − 1][C] ←Knapsack(n − 1, C, W, V, DP ) ifW[n]>Cthen
return DP [n − 1][C] ifDP[n−1][C−W[n]]=−1then
DP [n − 1][C − W [n]] ←Knapsack(n − 1, C − W [n], W, V, DP ) return max(DP[n−1][C −W[n]]+V[n],DP[n−1][C])
Note that the first and last algorithms have runtime and space complexities O(n · C), but the first approach generally saves on memory by avoiding unnecessary stack allocation, and the last generally saves on runtime because it only calculates the subproblems that are needed. On the other hand, the second algorithm has an exponential runtime complexity in the worst case, but its space complexity is O(n). In general, when considering algorithms, there tends to be a trade-off between asymptotic time complexity and memory usage; consider which is more relevant to the task at hand on practical problems.
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 3 To summarize:
Bottom-Up (Tabulation)
Top-Down (Recursion)
Top-Down (Memoization)
1. Almost always faster in practice
2. Does not run the risk of overflowing the stack
3. Most array-like structures can be further optimized 1. Easy to implement given a recurrence relation
2. No additional data structures necessary
3. Sometimes (although very rarely) the only option 1. Usually much better time complexity than the
purely recursive approach.
2. May save time if some value does not need
to be calculated
3. While harder to implement than pure recursion, the logic
may still seem more straight-forward than bottom-up
Finally, things to worry about (indirect disadvantages) when implementing each method: 1. Bottom-up
(a) Try to minimize work that is not needed. For example, if your result will only depend on even-valued entries, consider not tabulating the odd-valued entries at all.
(b) Sometimes you need to re-think the underlying dependencies between each sub-problem to find the best data-structure for this! Most of the time, however, a 1-D, 2-D, or 3-D array will suffice.
2. Top-down
(a) When doing Top-down, you are most likely using a lot of recursive calls, so take advantage of tail-recursion whenever possible!
(b) Be aware of edge cases. Only your base cases are guarding against seg fault.
1.3 An example of the 0-1 Knapsack recurrence
Suppose the knapsack has capacity 7 and the following list of items is available to fill the knapsack:
Number 1 2 3 4 5 Value 96532 Weight 64321
What is the maximum value that can be obtained from placing items in the knapsack? It turns out the value is 11 – and our recurrence gives us that answer as well.
We can view the following table as a memo which stores either the values previously queried or as a table which allows us to compute successive entries – either is fine, but the underlying rule behind how the table is filled is the recurrence relation. What changes between the two approaches is the order entries are filled. We present the way the iterative program fills the memo.
The state of table 1 captures the base cases of the recurrence. Question marks (?) indicate entries for which we have no information.
The state of table 2 captures the information we’d be interested in when we are trying to insert the first item and limit the capacity of the knapsack to 3. Because we cannot fit item 1 into the
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 3
table, we are in the case where the entry is determined by entry above this entry – this entry is in red.
The state of table 3 captures the information we’d be interested in when trying to insert the second item and limit the capacity to 6. In this case, we can fit the item inside the knapsack, so we are interested in the entries in the row 2 which consider the cases where we take the second item (in blue) and where we do not take the second item (in red). We compare (value of the blue entry + v2) to (value of the red entry) to determine which option is better. In this case, it is better to not take the second item, so we copy the value of the red entry into the cell.
The state of table 4 captures the information we’d be interested in when trying to insert the third item and limit the capacity to 7. In this case, we can fit the item inside the knapsack, so we are interested in the entries in the row 2 which consider the cases where we take the third item (in blue) and where we do not take this item (in red). We compare (value of the blue entry + v3) to (value of the red entry) to determine which option is better. In this case, it is better to take the second item, so we copy (value of the blue entry + v3) into the cell.
Knapsack capacity 01234567 none 0 0 0 0 0 0 0 0 10??????? 20??????? 30??????? 40??????? 50???????
Knapsack capacity 01234567 none 0 0 0 0 0 0 0 0 1000????? 20??????? 30??????? 40??????? 50???????
Table 1: Information before all computation Table 2: Information when inserting item 1
Knapsack capacity 01234567 none 0 0 0 0 0 0 0 0 100000099 2000066?? 30??????? 40??????? 50???????
Knapsack capacity 01234567 none 0 0 0 0 0 0 0 0 100000099 200006699 30005669? 40??????? 50???????
Table 3: Information when inserting item 2 Table 4: Information when inserting item 3
2.1 Introduction
Greedy Algorithms
Greedy algorithms are intuitive ways to solve problems. Just imagine eating a cake: you start with the best possible piece, then the next best, and so on… until you eat the whole cake! Of course, imagining eating the entire cake does not guarantee that things will always go so well…
2.2 Important Tips
Note that devising greedy algorithms for a wide range of problems is not always straightforward or easy. Here are a few tips to keep in mind:
Items allowed Items allowed
Items allowed Items allowed
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 3
• There is no single method of devising greedy algorithms that generalizes to every problem. Understanding what “greedy” means varies among problems and even among different interpretations of the same problem.
• The solution to a greedy algorithm is not necessarily optimal. Consider a greedy algorithm for the 0-1 knapsack problem which selects the item with the highest value at each step. Can you construct an example where this would not be optimal, i.e. where you can obtain a higher total value using a selection of items that is different than what is returned by this greedy approach? In fact, sometimes greedy algorithms can give you extremely suboptimal solutions.
• You must prove that your greedy algorithm is optimal. While we may cover some examples of proving the optimality of specific greedy algorithms, again, there is no general proof methodology that applies to all greedy algorithms.
• Greedy algorithms can be a useful heuristic for problems. A heuristic is any approach to problem solving that is practical (fast/easy) to reach an immediate goal, such as finding an approximate solution to a problem, but does not guarantee the solution to be optimal. Greedy algorithms are often the first approach used to work toward a solution to new problems in computer science.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com