Optimal algorithm for a splitting problem
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2

Thread: Optimal algorithm for a splitting problem

  1. #1
    Join Date
    Oct 2009
    Posts
    1

    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.

    All numbers are power of 4, except the price, because it can be optional. The minimum value is 4^0 and the maximum is 4^11.

    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!

  2. #2
    Join Date
    Oct 1999
    Location
    ks
    Posts
    502

    Re: Optimal algorithm for a splitting problem

    if i understand the problem correctly what you need to do is set up an exhaustive set of possibilities and simply use a "champion - challenger" approach to finding the least cost solution.

    solution list:

    parts: 1 4 16 64 256
    0 0 0 0 1
    0 0 0 4 0
    0 0 4 3 0
    0 0 8 2 0
    ...

    256 0 0 0 0

    these solutions need to have total prices computed.

    this was set up for 256 as unit - you need to set up for 1024.

    presumably this is an excercise to set up loops or recursive processes to generate the next solution.
    Last edited by jim enright; October 4th, 2009 at 09:54 AM. Reason: mistake

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center