1
$\begingroup$

My question is actually very similar to this other one: Given a vector of positive integers, count the number of combinations which have a sum that produces a different value. But, since this previous question did not get much attention, I've preferred to reformulate it according to my context rather than edit it.

Consider a 0-1 knapsack problem with $n$ items $\{1, \dots, n\}$, in which all weights $(w_1,\dots,w_n)$ are positive integers. Also assume that there is a known upper bound $w_\max$ for the weight of each item, that is: $w_i \le w_\max, \forall i$.

I've read the following statement in a paper that uses the knapsack structure I've just described:

The total number of different possible weights (resulting from —randomly— selecting a subset of items and adding up the weights of all items in that subset) is less than or equal to $n w_\max$.

[NOTE: The case in which no item is chosen is omitted, in the context where this paper comes from.]

My question (not to simple to be posted here, I hope): How does that upper bound come up? Where does it come from?

I mean, I guess it is a known upper bound in the context of knapsack problems with integer weights, as the authors of that claim do not give any reference for it. Moreover, I know that there is an algorithm based on dynamic programming which is able to solve this problem in $\mathcal{O}(n w_\max)$ time. That is why I am asking if anyone here has seen this before and can give me either an explanation or a reference about it (I mean, about the number of different resulting weights; not about the computational complexity, although I guess it may be somehow related).

I know that the number of possible combinations would be (excluding the case in which no item is chosen) $\sum_{k=1}^n\binom{n}{k} = 2^n-1$. Now, assuming that weights can only take positive integer values, the number of possible different resulting weights could be much lower than this general bound $2^n-1$ if $w_\max$ is small enough. But I am not able to deduce how this upper bound $n w_\max$ appears by myself.

EDIT:

The question is so easy to answer... I've got one answer in the comments section. I think I am not used to think in integer mode.

So, I ask the moderators to close this question, if they think it should be.

$\endgroup$

closed as off-topic by Gerry Myerson, Chris Godsil, Max Alekseyev, Wolfgang, Stefan Kohl Oct 13 '16 at 17:18

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Gerry Myerson, Max Alekseyev, Wolfgang, Stefan Kohl
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ All obtained weights are positive integers not exceeding $nw_{\max}$. Is it of research level? $\endgroup$ – Ilya Bogdanov Oct 13 '16 at 10:40
  • $\begingroup$ @IlyaBogdanov Oh, I see... Since all obtained weights are positive integers not exceeding $n w_\max$, there can be at most a different number of $n w_\max$ of them... So easy... $\endgroup$ – Vicent Oct 13 '16 at 10:47