Find combinations or $n$ items that add up to $x$ out of $p$

Question

I have a list of $313$ items, each item with a value associated (items are unique but values are not):

Item: A, Value: 127
Item: B, Value: 84
Item: C, Value: 23
Item: D, Value: 45
Item: E, Value: 127
Item: F, Value: 56
...

I need to find all combinations of $8$ items for which the value adds up to $855$ items.

I started working this out by brute force but soon realized there are $2,087,706,718,701,747$ possible combinations so it is not feasible to just wait for the computer to calculate it.

I have looked into similar questions but they all deal with very small numbers and can be easily calculated by brute force.

I don't know where to even start to look at different approaches to solve the problem.

$1.$ What is the best approach to solve this problem?

$2.$ Is there a similar problem someone could point me to that I have not found?

Answer 1

I think this can be done by depth-first search in a reasonable amount of time. I will first describe an approach on the assumption that there are no duplicate values, and then discuss how to modify it to address duplicates.

Sort the items in increasing order of value, and then do a typical depth-first search to choose subsets of $8$ items with total value exactly $858$. Since the values increase, we know for example, that the first item cannot have a value greater than $\lfloor858/8\rfloor=107.$ Suppose the first item added has value $50$. Then then second item can have value at most $\lfloor(858-50)/7\rfloor=115$, and so on.

Using this "test and generate" approach instead of "generate and test" should produce substantial savings.

We could use the method without change when there are duplicate values, but it adds unnecessary work. If items A and B both have value $42$ then almost all the work done when A is allocated as the first item will be duplicated when B is allocated as the first item, the only exception being when both are allocated. Unless there are very few duplicates it will pay to eliminate duplicates, but keep track of the number of occurrences of the value. In the depth first search, you would allow allocation of the previous value, so long as it hadn't already been used the maximum number of times.

Then you would have the problem of how to report the duplicates. Is it enough to say "Pick $3$ items of value $63$," or must you generate all $3$-subsets of items with value $63?$. Either way, you'll be able to deal with it.

I have a further idea that I would be very inclined to use. There's no way to tell in advance if it will be worthwhile, but I think it has the potential to provide a good return at relatively low cost.

Find all the numbers less than $858$ that can be express as a sum of $4$ of the values (allowing for duplicates.) Then a sum $n\leq858/2=429$ is admissible if and only if $858-n$ is also one of the sums. In the depth-first search, when you get to level $4$, if the total value so far is not admissible, you backtrack.