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.