Find N best subset of quotations
This problem is $\textrm{NP}$-hard by a reduction from (the decision version of) set-cover: given an integer $k$, a set of items $I = \{x_1, \dots, x_n\}$ and a collection $S = \{S_1, \dots, S_m \} \subseteq 2^I$ of subsets of $I$, decide whether there is a subset $C$ of $S$ such that $|C| \le k$ and $\bigcup_{S_j \in C} S_j = I$.

Given an instance of set-cover, we can reduce it to your problem as follows:


There are $n$ packages to be shipped. Each package has a unique combination of weight class and category. For simplicity you can think of all the packages being in same category but having different weight classes. I will denote by $W_i$ the weight class of the $i$-th package.
There are $m$ shipping companies. The $j$-th shipping company ships a package of weight class $W_i$, with $x_i \in S_j$, for a cost of $\varepsilon &lt; \frac{1}{n}$ and a package of weight class $W_i$, $x_i \not\in S_j$, for a cost of $1$.
Pick $w = k$.


There is a set-cover of size at most $k$ iff the cost for shipping all the packages using at most $w$ companies is at most $\varepsilon n &lt; 1$.

Indeed, given a set-cover $C = \{ S_{j_1}, \dots, S_{j_\ell} \}$ of size $\ell &lt; k$ we know that $\bigcup_{i=1}^\ell S_{j_\ell} = I$, i.e., if we select the $j_1$-th, $j_2$-th, $\dots$, and $j_\ell$-th shipping companies, we can send each of the $n$ packages at a cost of $\varepsilon$.

On the other hand, if there is a way to send all the packages using at most $w$ shipping companies with a cost of at most $\varepsilon n &lt; 1$ then, for each of the $n$ packages, there must be at least one selected company that ships it with a cost of $\varepsilon$. In other words the sets $S_j$ corresponding to the selected companies are a set-cover of size at most $w = k$.

Notice that any solution has either a cost of $\varepsilon n$ or a cost of at least $1$. Choosing $\varepsilon$ small enough shows that this problem is also inapproximable (in fact, if a shipping cost of $0$ is allowed, you can directly set $\varepsilon = 0$).