determining which numbers in an array equal a specific sum

Question

I am presenting this question as a general math problem. I am going to tag it with Visual Basic, as the solution would likely be implemented in a spreadsheet.

I have a list of shipments with the number of widgets in each shipment. Each shipment was loaded on either Truck #1 or Truck #2. Given the total number of widgets on each truck, how can I determine which shipments were on each truck?

For example, here is the loading for total widgets in each truck:

Truck #1  83,240 
Truck #2  63,460 
         -------
         146,700

And here is a detailed shipment list.

SHIPMENT ID  QUANTITY 
90006           340 
93806         2,460 
93906        22,980 
92506         5,960 
96306         3,580 
96406         3,320 
96906         2,680 
97306         1,160 
99206         9,780 
95005        15,300 
95006         2,980 
96008        22,320 
95606        28,580 
90206         5,020 
90306         3,160 
94006         1,140 
94406         4,640 
94606         7,900 
98606         3,400 
            -------
            146,700

Which shipments were in Truck #1 and Truck #2?

My hobby: answering SO questions with XKCD cartoons...xkcd.com/287 — jtolle
– jtolle, Commented Sep 16, 2011 at 18:22
You might find my use of Excel's Solver in Excel formula needed to answer a similar problem useful. Espcially as it handles a closest solution if an exact solution does not exist — brettdj
– brettdj, Commented Dec 26, 2011 at 12:00

Community · Accepted Answer · 2017-04-13 12:19:15Z

5

This is a variation of the subset sum problem. More information can be found on Stack Exchange's Math site. This problem is not trivial. One algorithm is described at the Wikipedia page. In your case, an exhaustive search is probably appropriate.

edited Apr 13, 2017 at 12:19

CommunityBot

11 silver badge

answered Sep 16, 2011 at 13:57

Ishmael

32.8k4 gold badges41 silver badges49 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user191688 Over a year ago

Ah! The old subset sum problem. never heard of it. :) I can see from the link you provided that it is not trivial. Will look into it.

Zéychin Over a year ago

Note that for some sets, there may not be unique solutions, which, for this application, may prove to be a significant issue.

Collectives™ on Stack Overflow

determining which numbers in an array equal a specific sum

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related