COMP 582 GRADUATE DESIGN AND ANALYSIS OF ALGORITHMS Spring 2023 Homework #4
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Homework #4
COMP 582
GRADUATE DESIGN AND ANALYSIS OF ALGORITHMS
Spring 2023
Problem 1[1.5 marks]
There are n coins given by a list P = {p1 , . . . ,pn} where pi ∈ {1, . . . ,K} is the price of the coin i. Design an algorithm that checks if it is possible to break the set of all items P into two parts PA and PB such that PA n PB = P, PA ∩ PB = ∅ and 对i∈PA pi = 对i∈PB pi?
Problem 2 [1.5 marks]
Assume you want to spend exactly A dollars. There are t items where each of them has unlimited supply and they are worth C1,C2 , ...,Ct dollars accordingly. Design a dynamic programming algorithm to compute the number of ways to spend exactly A dollars.
For example, when A = 4 and C = {1, 2}, you have three ways: {1, 1, 1, 1}, {1, 1, 2}, {2, 2}.
2023-02-16