Permutation / combination problem :/

[asibin2000]

I have a unique problem that I need to code and I just can't get my head around it.

I have a list in descending order:

Points Cost Cost / Points
500 8000 16
470 7520 16
400 6400 16
350 5600 16
310 4960 16
270 4320 16
250 4000 16
210 3360 16
170 2720 16
150 2460 16.4
120 2028 16.9
100 1750 17.5
80 1432 17.9
65 1189.5 18.3
45 841.5 18.7
20 382 19.1
10 193 19.3
7 138.6 19.8
5 100.5 20.1
2 41.4 20.7
1 21.4 21.4

So the person has 300 points and I need to find out the most effective way to spend the 300 points.

So i've been breaking it down for each combination.. 270 + 20 + 10 = 300, 250+45+5 etc.. Then calculating the price based on that combination and then comparing which permutation has the best deal.

Does anyone have a formula I can use? Instead of making a massive matrix?

I know there is some match thing I can use but I just can't remember how to do it, let alone code it easily.

Any guidance would be greatly appreciated!

 

[mikrom]

Hi asibin2000,

Your problem seems to me to be similar to the problem with loading packages on the truck, which you can find here:

http://www.tek-tips.com/viewthread.cfm?qid=1513513&page=1

Try to set
your list of points = list of packages to be loaded
points the person should spend = max capacity of the truck

Isn't it the same?

 

[mikrom]

If I applied the truck loading algorithm to your problem I got this:

Original packages = [500, 470, 400, 350, 310, 270, 250, 210, 170, 150, 120, 100, 80, 65, 45, 20, 10, 7, 5, 2, 1]

Remaining packages = [500, 470, 400, 350, 310, 270, 250, 210, 170, 150, 120, 100, 80, 65, 45, 20, 10, 7, 5, 2, 1]
Now loading remaining packages on 1.Truck:
[COLOR=red]1.Truck loaded with packages [270, 20, 10] => total weight=300[/color]

Remaining packages = [500, 470, 400, 350, 310, 250, 210, 170, 150, 120, 100, 80, 65, 45, 7, 5, 2, 1]
Now loading remaining packages on 2.Truck:
[COLOR=red]2.Truck loaded with packages [250, 45, 5] => total weight=300[/color]

Remaining packages = [500, 470, 400, 350, 310, 210, 170, 150, 120, 100, 80, 65, 7, 2, 1]
Now loading remaining packages on 3.Truck:
[COLOR=red]3.Truck loaded with packages [210, 80, 7, 2, 1] => total weight=300[/color]

Remaining packages = [500, 470, 400, 350, 310, 170, 150, 120, 100, 65]
Now loading remaining packages on 4.Truck:
4.Truck loaded with packages [170, 120] => total weight=290

Remaining packages = [500, 470, 400, 350, 310, 150, 100, 65]
Now loading remaining packages on 5.Truck:
5.Truck loaded with packages [150, 100] => total weight=250

Remaining packages = [500, 470, 400, 350, 310, 65]
Now loading remaining packages on 6.Truck:
6.Truck loaded with packages [65] => total weight=65

Remaining packages = [500, 470, 400, 350, 310]
Now loading remaining packages on 7.Truck:
7.Truck loaded with packages [] => total weight=0

Remaining packages = [500, 470, 400, 350, 310]

So you see, you have 3 possible combinations how to spend exactly the 300 points...

Is this what you want?

 

[asibin2000]

Mikrom you rock

 

[asibin2000]

How would I implement this in other then python - I'm a bit confused I suppose with the language more then anything. I'm working with VBA / excel

 

[mikrom]

This is implemented using the recursion and the list datatype. You can implement that similary in other language - I could imagine Perl or Ruby, or any other language which supports recursion and a similar datatypes to lists, e.g. arrays.
I guess it must be possible in VBA too, but I don't know how to program in VBA / Excel

 

[macropod]

asibin2000

For a vba solution, see my post in:

http://www.tek-tips.com/viewthread.cfm?qid=1485698

Cheers

[MS MVP - Word]