We can easily reduce subset sum [1] to Problem 1 by using the second formulation ("given a set of integers and an integer s, does any non-empty subset sum to s?

We can easily reduce subset sum [1] to Problem 1 by using the second formulation ("given a set of integers and an integer s, does any non-empty subset sum to s?") and setting the integers to be the coin denominations and all the corresponding x_i equal to 1. So Problem 1 is NP-hard. [1] http://en.wikipedia.org/wiki/Subset_sum_problem http://en.wikipedia.org/wiki/Subset_sum_problem