动态规划解决背包问题.pdfVIP

The Knapsack Problem – an Introduction to Dynamic Programming Slides based on Kevin Wayne / Pearson-Addison Wesley Different Problem Solving Approaches Greedy Algorithms   Build up solutions in small steps   Make local decisions   Previous decisions are never reconsidered   We will solve the Divisible Knapsack problem with a greedy approach Dynamic Programming   Solves larger problem by relating it to overlapping subproblems and then solves the subproblems –  Important to store the results from subproblems so that they aren’t computed repeatedly   We will solve the Indivisible Knapsack problem with dynamic programming Backtracking   Solve by brute force searching the solution space, pruning when possible Slides based on Kevin Wayne / Pearson-Addison Wesley 2 The Knapsack Problem We are given:   A collection of n items   Each item has an associated non-negative weight, wi   Each item has an associated value (cost), ci   And we are given a knapsack that can hold total weight W Our task is:   Determine the set S of items of maximum total value (cost) that can be contained in the knapsack subject to the constraint that the total weight is no greater than W Slides based on Kevin Wayne / Pearson-Addison Wesley 3 The Knapsack Problem A first version: the Divisible Knapsack Problem   Items do not have to be included in their entirety   Arbitrary fractions of an item can be included   This problem can be solved with a GREEDY approach   Complexity – O(n log n) to sort, then O(n) to include, so O(n log n) KNAPSACK-DIVISIBLE(n,c,w,W) 1.  sort items in decreasing order of c /w i i 2.  i = 1 3.  currentW = 0