# Optimal algorithm for a splitting problem

• 10-02-2009
Optimal algorithm for a splitting problem
Hello everybody!

My problem is this:

I have a unit and lot of parts. All parts have a price. These parts create a unit, but lot of way can be exist to create a unit. For example:

The unit is 1024, and the parts are:

256 10
256 20
256 30
256 40
1024 98
1024 513

So, I can make a unit if I will add 256+256+256+256, and I have to pay for that 100. Or I will chose only 1024 and I have to pay for that 98. 98 is smaller than 100, so this will be an optimal solution.

Which algorithm does it solve this problem optimal, if the prices are incremental ordered and the units are ordered too, like in the example.

Be on the safe side, I show you an another example.

The unit is 256, and the parts are:

16 1
16 1
16 3
16 4
64 1
64 1
64 2
256 14

The optimal solution is 16+16+16+16+64+64+64, because 1+1+3+4+1+1+2=13, and 256 is 14.

Thank you!
• 10-02-2009
EVOEx
What are the constraints on all 3 numbers? What are their minimum and maximum values? Because I'm quite sure this is an NP problem. However, I do also believe that the solution you are expected to provide is a dynamic programming solution. But that's only possible if there is a constraint on those numbers which makes it acceptable for DP.
• 10-02-2009