0
$\begingroup$

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} $$

$\endgroup$
  • 1
    $\begingroup$ Incomprehensible. I haven't a clue what you are trying to do. $\endgroup$ – Gerry Myerson Mar 3 at 9:07
  • $\begingroup$ Can you please give an example of a non-scalar integer? $\endgroup$ – Marc van Leeuwen Mar 3 at 9:25
  • $\begingroup$ @GerryMyerson, Suppose there are 3 type of box, each can carry 6, 4, and 2 balls respectively. Trying to figure out how to carry 5 balls, using what combination of boxes (and how many). $\endgroup$ – Mr.EU Mar 3 at 9:26
  • 2
    $\begingroup$ @GerryMyerson: I think what OP is searching is the set of minimal natural-number linear combinations of the specified parts (entries of $V$) with value${}\geq N$ $\endgroup$ – Marc van Leeuwen Mar 3 at 9:27
  • 1
    $\begingroup$ Gerry suggests that you want the smallest possible sum $\ge N$, but the examples suggest to me that it's more complicated. Are you after the full set of sums such that no individual weight can be decreased without the sum falling below $N$? $\endgroup$ – Peter Taylor Mar 4 at 9:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.