recursive maximal combination

This is a discussion on recursive maximal combination within the C Programming forums, part of the General Programming Boards category; Originally Posted by newyork the problem doesnt allow me to change the array and i cant "iterate through the array" ...

  1. #16
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by newyork View Post
    the problem doesnt allow me to change the array
    and i cant "iterate through the array" because its not an itterative problem ,it a recursive problem
    There are no "recursive problems", only "recursive solutions"

    For each recursive step you have a count of how many items you have in your bag, plus a second array of booleans which remembers which of the items are already in the bag, plus a total of their weight.
    Then you have a loop of recursive calls, to try adding each of the unused items in the bag, one at a time, adjusting count and total for each call. For each call you update a global record of the best list of items, if the total is closer than the last remembered total.
    Your base cases are that you've put more items in the bag than will fit, or when all items are in the bag and your bag is still not full.

    It's O(n!) but it's the only way to guarantee that you find the optimal solution. Look up the knapsack problem!
    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"

  2. #17
    Registered User
    Join Date
    Jul 2011
    Posts
    1

    Needed more usage of this solution

    If I have a list of items with different weights, and each bag can have maximum weight (let say 10), I need another code based on this code in order to find the minumum number of bags needed to fill all items.

    Since I'm not a very proffesional of writting C, I appriciate a code.

    My approch of solving the problem is :
    Each time I find a combination fits in a bag, find all combination from the rest of items not chosen in that combination, recursively.
    When there is no more items in list, save this is a set of combination.
    After finding all sets, I need to find the minumum set.

  3. #18
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,742
    > After finding all sets, I need to find the minumum set.
    Except you don't need to record all the sets, only the smallest you found so far.
    If the new one is smaller still, you keep the new one.

    Oh, and bumping old threads with "please send me code" is frowned on - we're not a coding service.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  4. #19
    Registered User
    Join Date
    May 2009
    Posts
    2,745
    @rabehma:

    Take the total mass of the Objects divided by max per bag; this will be the best case answer on number of bags.
    If you get the best case answer on number of bags, you can stop looking.
    Note: Most of the time it is likely that the " best case answer" is not possible.

    Tim S.

  5. #20
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by stahta01 View Post
    @rabehma:

    Take the total mass of the Objects divided by max per bag; this will be the best case answer on number of bags.
    If you get the best case answer on number of bags, you can stop looking.
    Note: Most of the time it is likely that the " best case answer" is not possible.

    Tim S.
    Hi Tim...

    Real world adaptation... Take best case answer (as above) and add 1... 'cause you know you will never get a "best case result".

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. recursive function
    By technosavvy in forum C Programming
    Replies: 1
    Last Post: 02-29-2008, 05:42 AM
  2. difference between recursive and iterative
    By Micko in forum C Programming
    Replies: 33
    Last Post: 07-06-2004, 10:34 PM
  3. Algorithm help (Changing from Recursive to Non Recursive)
    By Thantos in forum C++ Programming
    Replies: 1
    Last Post: 04-25-2004, 08:27 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. How to change recursive loop to non recursive loop
    By ooosawaddee3 in forum C Programming
    Replies: 1
    Last Post: 06-24-2002, 09:15 AM

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