You have a set of coins. Each coin i has value vi . Your goal is to find a set o

Question

You have a set of coins. Each coin i has value vi . Your goal is to find a set of coins with total value exactly equal to V . You can use only one copy of each coin. Design a dynamic programming algorithm to determine whether it is possible to accomplish this. You don’t need to output which coins are used, just whether it is possible or not. Hint: this is similar to, but not the same as, the knapsack problem without item repetition. Like the edit distance problem and the knapsack without repetition problem, draw a 2-dimensional Directed Acyclic Graph. Define P(i, W) = True if you can get value W using coins 1, ..., i. How do you calculate P(i, W) using subproblems?

Treat single arithmetic operations (addition, subtraction, multiplication, and division) as constant time operations.

Explanation / Answer

Duringarobbery,aburglarndsmuchmorelootthanhehadexpectedandhastodecidewhat to take. His bag (or “knapsack”) will hold a total weight of at most W pounds. There are n items to pick from, of weight w1,...,wn and dollar value v1,...,vn. What’sthe most valuable combinationofitemshecantintohisbag?1 Forinstance,take W = 10 and Item Weight Value 1 6 $30 2 3 $14 3 4 $16 4 2 $9 There are two versions of this problem. If there are unlimited quantities of each item available, the optimal choice is to pick item 1 and two of item 4 (total: $48). On the other hand, ifthere isone of eachitem (the burglarhasbrokeninto anart gallery,say),then theoptimal knapsackcontainsitems1and3(total: $46). AsweshallseeinChapter8,neitherversionofthisproblemislikelytohaveapolynomialtime algorithm. However, using dynamic programming they can both be solved in O(nW) time, which is reasonable when W is small, but is not polynomial since the input size is proportionalto logW ratherthan W. Knapsackwithrepetition Let’s start with the version that allows repetition. As always, the main question in dynamic programming is, what are the subproblems? In this case we can shrinkthe original problem in two ways: we can either look at smaller knapsack capacities w W, or we can look at feweritems(forinstance,items 1,2,...,j,for j n). Itusuallytakesalittleexperimentation togureoutexactlywhatworks. Therstrestriction callsforsmallercapacities. Accordingly,dene K(w) = maximumvalueachievablewithaknapsackofcapacity w. Can we express this in terms of smaller subproblems? Well, if the optimal solution to K(w) includes item i, then removing this item from the knapsack leaves an optimal solution to K(wwi). Inotherwords, K(w) issimply K(wwi) + vi,for some i. Wedon’tknowwhich i, soweneedtotryallpossibilities.
K(w) = max i:wiw{K(wwi) + vi}, where as usualour convention isthat the maximumover anempty set is 0. We’re done! The algorithmnowwritesitself,anditischaracteristicallysimpleandelegant.

Knapsackwithoutrepetition On to the second variant: what if repetitions are not allowed? Our earlier subproblems now become completely useless. For instance, knowing that the value K(w wn) is very high doesn’t help us, because we don’t know whether or not item n already got used up in this partial solution. We must therefore rene our concept of a subproblem to carry additional informationabouttheitemsbeingused. Weaddasecond parameter, 0 j n: K(w,j) = maximumvalueachievableusingaknapsackofcapacity w anditems 1,...,j. Theanswerweseek is K(W,n). Howcanweexpressasubproblem K(w,j) intermsofsmallersubproblems? Quitesimple: eitheritem j isneededtoachievetheoptimalvalue,oritisn’tneeded: K(w,j) = max{K(wwj,j 1) + vj,K(w,j 1)}. (The rst case is invoked only if wj w.) In other words, we can express K(w,j) in terms of subproblems K(·,j 1). The algorithm then consists of lling out a two-dimensional table, with W + 1 rows and n + 1 columns. Each table entry takes just constant time, so even though the table is much largerthaninthepreviouscase,therunningtimeremainsthesame, O(nW).

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.