Optimal algorithm for a splitting problem

This is a discussion on Optimal algorithm for a splitting problem within the C++ Programming forums, part of the General Programming Boards category; Hello everybody! My problem is this: I have a unit and lot of parts. All parts have a price. These ...

  1. #1
    Registered User
    Join Date
    Oct 2009
    Posts
    2

    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!

  2. #2
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    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.

  3. #3
    Registered User
    Join Date
    Oct 2009
    Posts
    2
    Hello!

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

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,295
    Well given those constraints I think it is far from being NP.
    In fact I'm pretty sure I've figured out how to do it in O(n) time with respect to the number of parts, given the list of parts is already sorted initially by part number then price. The powers of four bit is what makes that possible.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,295
    Oh by the way, I'm not sure what you're thanking us for yet. We may by chance tell you what it is you're wanting to know about this problem, but you'd be better off actually asking the question you want an answer to.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  2. Replies: 5
    Last Post: 12-03-2003, 04:47 PM
  3. Replies: 1
    Last Post: 11-17-2002, 09:52 AM
  4. problem with output
    By Garfield in forum C Programming
    Replies: 2
    Last Post: 11-18-2001, 07:34 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21