# Random knapsack algorithm: Select n positive integers that sum up to S

Problem to solve:

• Have a list of M products (eg 100000) with various prices.
• I want to randomly select n products(eg 10) that their sum of prices is S(eg. 100).
• Duplicates are allowed or not, does not matter.

Intrigued by a question on stackoverflow, I provided the following algorithm:

Considering the following:

In a collection of n positive numbers that sum up to S, at least one of them will be less than S divided by n (S/n).

Based on the above, you can break this down a set of steps:

1. Select a product randomly where price < S/n. Get its price, lets say X.
2. Select a product randomly where price < (S - X)/(n-1). Get its price, assume Y.
3. Select a product randomly where price < (S - X - Y)/(n-2).

Repeat this (n-1) times and get (n-1) products. For the last product, select one where price = remaining price. (or order products by price descending with the condition of price <= remaining price and hopefully you could get close to the sum).

Alternatively, you could get (n-2) products and them find 2 products that sum to the remaining price to get better results.

Using code to construct the problem and run it, it produces a result set and also it appears fast.

My questions:

• is the logic correct?
• is it random or is there a bias to it? Lets say we could produce all the different combinations of products that sum to S, will the above approach have equal possibility to produce any of the result sets?
• Can it be improved?
• Bonus: What is the cost? Its complexity in term of computations needed.

From a comment on the original question, the problem seem be equivalent to the knapsack problem where prices are the numbers and # products on each price is its weight.

• "at least one of them will be less than $\frac{S}{n}$" unless they're all equal to $\frac{S}{n}$. – David Diaz Jun 8 '18 at 13:03

Probably not random. Assume $S \equiv$ 1 mod d for some integer d. Further assume that all of your prices $p_{i}$ happen to be divisible by d except $p_{1}$ and $p_{n}$, (the smallest and largest) which are both $\equiv$ 1 mod d. Then your n products must include either $p_{1}$ or $p_{n}$ but not both. Since you are always picking elements from the smaller half of the set, the largest element can only be selected in the last step in the cases when the smallest has not already been selected.