Intro to algorithm.

Graded Problem (Page limit: 1 sheet; 2 sides) A bandit has broken into a store and has found many items he wants to bring with him and then flee the scene. There are n items, of positive integer sizes s1, 82, , Sn. Each item has a positive value to him, vi, v2,. .. ,vn Being greedy the bandit would have liked to bring everything, but for the fact that his getaway car has only a limited capacity that can hold a total size at most S. Therefore his problem is to select a subset A-{1, 2, . . . ,n} such that the sum EA Si-S and the total value (his total loot) Ui iEA s maximized Find a Dynamic Programming algorithm to solve this problem. Your solution should have worst case running time polynomial in s1, 82, ..., Sn, vi, v2, , Un, and S Analyze its running time. Prove your algorithm is correct, and runs in your stated time. (Hint: Suppose his total capacity is S - 1?)