Does the problem of finding minimal weighted sums above a threshold have a name?

33 Views Asked by At

Does the following problem have a name?

Let $N$ be a positive integer (the threshold) and let $V$ be a set of positive integers.

A weighting is a function from $V$ to non-negative integers, and the value of weighting $w$ is $\sum_{v \in V} w(v) \cdot v$. A weighting can be thought of as a representation of a partition of its value into parts drawn from $V$.

There is a natural partial order on weightings: $w_1 \le w_2$ iff $\forall v \in V: w_1(v) \le w_2(v)$.

A weighting is admissible if its value is at least $N$.

The problem consists of finding the minimal admissible weightings: that is, all admissible weightings $w$ for which there is no admissible weighting $w' < w$.


Example: $N=5$, $V=\{6, 4, 2\}$. The minimal admissible weightings are:

$$ \begin{array}{c c c|l} w(6) & w(4) & w(2)& \textrm{value} \\ \hline 1 & 0 & 0 & 6 \\ 0 & 2 & 0 & 8 \\ 0 & 1 & 1 & 6 \\ 0 & 0 & 3 & 6 \end{array} $$

Example: $N=65$, $V=\{200, 100, 50\}$. The minimal admissible weightings are:

$$ \begin{array}{c c c|l} w(200) & w(100) & w(50) & \textrm{value} \\ \hline 1 & 0 & 0 & 200 \\ 0 & 1 & 0 & 100 \\ 0 & 0 & 2 & 100 \\ \end{array} $$