tailieunhanh - Thuật toán Algorithms (Phần 50)

Tham khảo tài liệu 'thuật toán algorithms (phần 50)', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 37. Dynamic Programming The principle of divide-and-conquer has guided the design of many of the algorithms we ve studied to solve a large problem break it up into smaller problems which can be solved independently. In dynamic programming this principle is carried to an extreme when we don t know exactly which smaller problems to solve we simply solve them all then store the answers away to be used later in solving larger problems. There are two principal difficulties with the application of this technique. First it may not always be possible to combine the solutions of two problems to form the solution of a larger one. Second there may be an unacceptably large number of small problems to solve. No one has precisely characterized which problems can be effectively solved with dynamic programming there are certainly many hard problems for which it does not seem to be applicable see Chapters 39 and 40 as well as many easy problems for which it is less efficient than standard algorithms. However there is a certain class of problems for which dynamic programming is quite effective. We ll see several examples in this section. These problems involve looking for the best way to do something and they have the general property that any decision involved in finding the best way to do a small subproblem remains a good decision even when that subproblem is included as a piece of some larger problem. Knapsack Problem Suppose that a thief robbing a safe finds N items of varying size and value that he could steal but has only a small knapsack of capacity A4 which he can use to carry the goods. The knapsack problem is to find the combination of items which the thief should choose for his knapsack in order to maximize the total take. For example suppose that he has a knapsack of capacity 17 and the safe contains many items of each of the following sizes and values 483 484 CHAPTER 37 name A B C D E size 3 4 7 8 9 value 4 5 10 11 13 As before we use single letter names for the items .