Minimum multi-subset sum to a target

Assuming that the numbers are positive integers,

This is closely related to the Frobenius Coin Problem which says that there is a maximum number $\displaystyle F$ (called the Frobenius number) which is not representable. It is NP-Hard to find out the Frobenius number when there are at least $\displaystyle 3$ numbers.

For a formula like approach to determine if such a representation is possible or not, you can use generating functions, which can be used to give a pseudo polynomial time algorithm, polynomial in size $\displaystyle W = n_1 + n_2 + \cdots + n_k$.

If the numbers are $\displaystyle n_1, n_2, \dots, n_k$ and you need to see if they can be summed to $\displaystyle S$ then the number of ways it can be done is the coefficient of $\displaystyle x^S$ in

$$\displaystyle (1+x^{n_1} + x^{2n_1} + x^{3n_1} + \cdots )(1+ x^{n_2} + x^{2n_2} + x^{3n_2} + \cdots ) \cdots (1 + x^{n_k} + x^{2n_k} + x^{3n_k} + \cdots )$$

$$\displaystyle = \dfrac{1}{(1-x^{n_1})(1-x^{n_2}) \cdots (1-x^{n_k})}$$

Using partial fractions this can be written as

$$\displaystyle \sum_{j=1}^{m} \dfrac{C_j}{c_j - x}$$

where $\displaystyle C_j$ and $\displaystyle c_j$ are appropriate complex numbers and $\displaystyle m \le n_1 + n_2 + \cdots + n_k$.

The coefficient of $\displaystyle x^S$ is thus given by

$$\displaystyle \sum_{j=1}^{m} \dfrac{C_j}{c_j^{S+1}}$$

which you need to check is zero or not.

Of course, this might require quite precise floating point operations and does not actually tell you what numbers to choose.

SUBSET-SUM is NP-complete, so in general it's difficult to tell even if there is a choice of numbers that adds up to a given target.

EDIT: Moron has raised the valid point that numbers can be reused. We therefore replace each number $x$ with a sequence $x,2x,4x,\ldots,2^kx,\ldots$, stopping before reaching a number larger than our target.

Let's carefully analyze the blowup in size. Suppose the original numbers $x_i$ had size $l_i$, and the target $T$ had size $L$. We replace each number $x_i$ with $L$ numbers of size at most $L$, and so the new size is $$\sum_i L^2 + L \leq L^2 (\sum_i x_i + L),$$ so the blowup is at most cubic, and in particular polynomial. So the problem is still NP-hard (it is trivially in NP): no, since the reduction is in the wrong direction... (thanks, Moron, for noticing)