reset("0","0","1000","780","Dynamic Programming") # conf.lec \macro(S1,S) \macro(S1b,S) \macro(T1,T) \macro(T1b,T) B2s.hide() S! Dynamic programming is an algorithm design strategy especially - useful for solving - Optimization Problems. S! B2- Optimization Problem: "Find an object x satisfying certain - constraints and such that Cost(x) is minimum over all x satisfying the - constraints." S! Here are some examples. S! B2:: Example 1: Tailor's layout problem. Given a set of - geometric shapes and a seminfinite roll of cloth of some given width - W, place them onto the roll without overlap such that the length L - that must be cut out of the roll to accomodate them should be minimized. B2:: x = layout, Cost(x) = length L that must be cut from the roll. B2:: Example 2: Travelling salesman problem. Given a weighted - graph in which each edge - represents the time required to travel from vertex i to vertex j, find - a permutation of the vertices such that if you travel in the graph - according to the permutation, and return to the vertex you started - with, the total distance covered is minimized. B2:: x = permutation. Cost(x) = Length of entire path indicated by x. S! We next define some commonly used terms. S! B2:: Feasible solutions: All x satisfying the constraints. B2: Optimal solutions: That x satisfying the constraints and - having minimum Cost(x) S! Sometimes Optimization problems will be stated with a function - Benefit(x) which is to be maximized. We could of course define -
Cost(x) = - Benefit(x)
and use our method here. S:: Our next example, which we will study in detail requires us to maximize benefit. S! B! Knapsack problem: Given a set of n items having values V[1,...,n] and weights W[1,...,n] respectively, and a knapsack having capacity C, find a subset of items whose total weight is at most C and whose total value is maximum over all possible subsets. B:: x = subset of {1,...,n}. Benefit(x) = value of items in x. S! At first glance you might think this problem is easy. "Simply select items in increasing order of value"... B2!