all possible combinations

Question

I have a math problem that goes as follows:

I have a container which holds a total of 21000 kilos. I have 4 items A,B,C,D .

Item A weights 1 kilo. Item B weights 4 kilos. Item C weight 5 kilos. Item D weights 5 kilos also.

I am looking for an algorithm that will iterate through all possible combinations keeping the above equation. for example:

{20000 , 0, 0, 200} --> 20000*1 + 0*4 + 0*5 + 200*5 = 21000 kilos.

{19996, 1, 0, 200} --> 19996*1 + 1*4 + 0*5 + 200*5 = 21000 kilos.

Are you sure you want to iterate over all possible combinations? What exactly are you trying to do? Solve the knapsack problem? http://en.wikipedia.org/wiki/Knapsack_problem — Larry Wang, Jul 14 '10 at 19:07
What are you going to do with the tens or hundreds of thousands of solutions? — David Thornley, Jul 14 '10 at 19:16
If it's homework then it's very weird. Homework problems usually give you `N` kilos, not ... 21000. — IVlad, Jul 14 '10 at 19:36
haha..guys school was done years ago. i wish! To answer your questions: I am solving this just for the fun of it. yes this is fun for me:) — Ray, Jul 14 '10 at 20:19

score 1 · Answer 1 · edited Jul 26 '12 at 09:34

1

You have to solve a + 4b + 5c + 5d = 20000 (a,b,c,d >=0)

or a + 4b = 2000 - 5e = 5(400-e) where e = c + d

so a + 4b can be 0, 5, 10, 15, 20, ..., 2000

you can easily find all possible values of a and b from above

after that you know the value of e = c + d, from there you can easily find all possible values of c and d.

edited Jul 26 '12 at 09:34

pmaruszczyk

answered Jul 25 '12 at 20:04

user1550193

score 1 · Accepted Answer · answered Jul 14 '10 at 19:09

1

This is very similar to the "Counting Change" example from SICP. See:

Example: Counting Change

answered Jul 14 '10 at 19:09

bshields

It certainly is. Here's another post on it too: http://stackoverflow.com/questions/1106929/find-all-combinations-of-coins-when-given-some-dollar-value – James Santiago Jul 14 '10 at 19:18

2 Answers2