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.
