Finding the smallest composition of a natural number with limited basic set of summands W.l.o.g. I have a set of natural numbers
$$S = \{s_1, \ldots, s_n\}, \quad s_i \in \mathbb N$$
as well as an $x \in \mathbb N$ I would like to express as sum of $s_i$.

How do I find the smallest number of summands?

In other terms: How to find $\min{\{\lvert I \rvert: I \in \mathcal I\}} \subset \mathbb N$.
$$\mathcal I = \{I \in \mathcal P(S): \sum_{s_i \in I} s_i = x\}$$
Hint: The naive ansatz to start with the biggest $s_i$ that is just smaller/equal $x$ and continue with $x-k \cdot s_i$, $k\in \mathbb N$ fails as you can see with: $S = \{2, 5, 9\}$ and $x = 10$.

Edit: The notation states a set of distinct summands—and neglects the question of existence of such a partition—but I'd be interested in approaches for non-distinct $s_i$ as well. :-)
 A: Assumptions:


*

*You can use a summand more than once.

*The $s_i$ are in increasing order.


Notation:
Define $M(x)$ as the minimum number of summands that you can use to add up to $x$. For convenience, define $M(0) = 0$.
Claims: (proof left to reader; there is a bit of cheat in here that some numbers may not be representable, so it is best to assume that $s_1=1$.)


*

*$M(x) = 1 + min \{M(x-s_i)\}$, where the minimum is taken over all $i$ with $s_i <= x$

*THIS STATEMENT IS INCORRECT (please see comment below) $M(x) = s_{n-1} + M(x-s_{n-1} s_n)$ for all $x \ge s_{n-1}s_n$  


From an algorithmic perspective, if your numbers are not too large, you can pre-compute $M(x)$ for $x \in \{1\ldots s_{n-1}s_n\}$, using the second claim to take care of larger numbers. If this gets too large to store, then you need to look at some sort of time-memory trade-off in computation.
A: Assuming the summands are drawn from a finite set $\{s_1,s_2,\ldots,s_n\}$ of positive integers, and that these may be repeated as often as desired, the problem of finding a shortest "addition chain" that reaches a given target $t$ can be formulated as an integer programming problem:
$$ \min X = x_1 + x_2 + \ldots + x_n $$
subject to $\sum_{i=1}^n x_i s_i = t$ and non-negativity of integers $x_i \ge 0$.
As Jeremy Dover pointed out, it is expeditious to remove any common factor of all the potential summands $s_i$, since for the target $t$ to be expressed as such a summation, that common factor must divide $t$, and furthermore removing the common factor from $t$ and each $s_i$ reduces the solution to a case where the $s_i$ collectively have greatest common factor $1$.
Such a formulation does not immediately guarantee an efficient algorithm since as a class, integer programming problems are NP-hard.  However it helps put in perspective some of the ideas for finding solutions.
The LP-relaxation of this problem (allowing for non-integer $x_i$'s) is easily solved by setting $x_i = t/s_i$ for the largest of the $s_i$'s and other unknowns to zero.  This is essentially the idea that motivates the OP's "naive ansatz".  We will henceforth assume for simplicity the $s_i$'s are ordered, so that $s_n$ is the largest of these.
In practice it may be straightforward to fix up such a non-integer solution to give one having all integer values $x_i$.  If a solution exists, we must have:
$$ \sum_{i\lt n} x_i s_i \equiv t \bmod{s_n} $$
In this vein we may look for the solution to our original problem by trying to solve the smaller problem of expressing a target $t-ms_n$ as a shortest summation with (repeated) summands from $S\setminus \{s_n\}$.  Choosing a felicitous integer value for $m\ge 0$ will produce the solution of our original problem, taking $x_n = m$ and other $x_i$ as found in the reduced problem.
Readers may find it convenient to think of searching for the solution working "backward" from target $t$ by a succession of "shortest paths" defined by edges that subtract an $s_i \lt s_n$ until a multiple $ms_n$ of $s_n$ is reached.  A best solution minimizes the combined sum of the length of path and $m$, since this will in turn be the sum of the $x_i$'s in the original problem.  Among shortest paths that reach a multiple of $s_n$ having a specific length, the best is the one that reduces $t$ the most (and thus gives the least $m$).
Note that the version of the problem in which summands may be repeated as many times as desired is the Change-making problem, and the procedure we just outlined is easily related to a dynamic-programming approach to that.

Next let us consider the version in which summands are distinct and may only be used once.  This is a version of the classic Subset Sum Problems since we seek a smallest subset of $S$ that sums to $t$.  These decision problems alone (does a subset with the target sum exist?) are NP-complete.
Readers may again find it convenient to think in terms of a shortest path formulation.  Starting from target $t$ we attempt to find the shortest path to zero along edges that subtract an allowed summand $s_i$.  This graph path problem is simplified by the application of Hobson's choice, since we either use the summand $s_i$ once or never at all.  Declining to use $s_i$ at some point in our search tree entitles us never to reconsider using it at a subsequent point in the search tree, although we may "backtrack" to that point and reconsider, as iterative deepening of depth-first search is used to simulate breadth-first search.
A very similar Question, An algorithm to find $X$ numbers that sum up to a given value, was asked in $2014$.  
Assume as before that the possible summands $s_i$ have been sorted.  For small values of $X$, the (minimum) number of summands used, it is well-known that for $X=1$ there is an optimal solution by binary search in $O(\ln n)$ and for $X=2$ by a variant of saddleback search in $O(n)$.
The best known algorithm for the Subset Sum Problem, which does not promise a subset of smallest size but only a decision if a subset sum equals the target, is that of Koiliaris and Xu(2015), "A Faster Pseudopolynomial Time Algorithm for Subset Sum", which has complexity $O(t\sqrt{n})$.
