Divide $n$ gifts among three people so as to minimize the difference in the total cost of gifts between the most lucky and the most unlucky people
Say your best answer so far has a difference D, and you can give w/3 - a to the first person. The best result you can have is w/3 + a/2 to the other two, giving a difference of 3a/2, so you only proceed if 3a &lt; 2D (actually, you will distinguish cases depending on w modulo 3 if all sizes are integers). 

Then you pick items for the second person. If you can give them w/3 - b, b ≥ a, then diff = a + 2b, so you need a + 2b &lt; D, or b &lt; (D - a) / 2; only if a ≤ D/3. If you can give them w/3 - b, 0 ≤ b ≤ a, then diff = 2a + b, so you need b ≤ D - 2a, only if a ≤ D/2. You analyse the case w/3 + b for the second person as well, so you find a range for how much goes to the second person. 

Problem is that you waste a lot of time with sets for the first person that are not particularly close to w/3. Based on the number of items and their values I'd make an estimate how good the best solution would be (how much the smallest D will be) and only look for items for the first person that might give a result &lt; 2D, then extending to 4D, 8D etc. if nothing is found.

And you should check the case where one item is > w/3 first, or you might waste a lot of time.