PHP查找内部数组中的总和的所有组合

Question

I'm writing a PHP script for available rooms in a hotel. I want every combination for a group (i.e. 4 person). This is my array.

$room_array = array(
    array(
        "title"         => "1 person room",
        "room_for"      => 1,
        "price"         => 79
    ),
    array(
        "title"         => "2 person room with other",
        "room_for"      => 1,
        "price"         => 69
    ),
    array(
        "title"         => "2 person room alone",
        "room_for"      => 1, 
        "price"         => 89
    ),
    array(
        "title"         => "2 person",
        "room_for"      => 2,
        "price"         => 69
    ),
    array(
        "title"         => "3 person",
        "room_for"      => 3,
        "price"         => 69
    )
);

Possible outcome:

• 4x 1 person room
• 4x 2 person room with other
• 3x 1 person room + 1x 2 person room with other
• 2x 2 person room
• 1x 3 person room + 1x 1 person room

etc. etc.

This calls for a recursive function. But every example I looked at doesn't work with counting in the inner array. The closest i found was this question:

Finding potential combinations of numbers for a sum (given a number set to select from)

But i didn't get de solution to work..

UPDATE:

Hi, thanks for all the answers. Really helped me in finding the best practice. In the meantime, the assignment has changed a little so I can't answer my own original question. My problem is solved. Thanks again for the help!

Answer 1

If you need all the combinations then you can use an backtracking iterative algorithm (depth path).

In summary:

1. Type of tree: binary tree because all the levels can contain a solution when the number of persons contabilized = objetive

   Binary tree

2. Algorithm functions You need to increment the cont every time that a level is generated with the number of persons of the level and decrement when you change your track (exploring brothers or back)

solution: array[0..levels-1] values {0 (node not selected) ,1 (node selected)}

solution[0] = 1 -> You choose that "1 person room" belongs to the solution

solutions: list/array of objects and every object contains array of titles of rooms

function Backtracking ()
    level:= 1
    solution:= s_initial
    end:= false
    repeat
         generate(level, solution)
         IF solution(level, solution) then
           save_solution
         else if test(level, solution) then
            level:= level+ 1
         else
            while NOT MoreBrothers(level, solution)
               go_back(level, s)

    until level==0

2.1. Generate: generate next node

2.2. Solution: test if it's a solution

2.3. Critery: if we must continue by this track or bound

2.4. MoreBrothers: if there are nodes without check at this level

2.5. Backtrack: all the nodes at this level were explored

2.6. Save solution: add to the solutions array your object that contains strings