CODEWITHSUNDEEP
algorithm
FlechMe
FlechMe

Reputation: 333

Possible combination of rooms for a product

I have a product with many kinds of rooms available and customizable. For exemple :

When a customer order a product (a travel), he give us a number of participants (for example : 2 adults and 2 childs...)

I have to give the customer the ability to choose a combination of kinds of rooms. with our example, we should have :

And at this point, I don't know what to do !

Upvotes: 1

Views: 125

Answers (1)

amit
amit

Reputation: 178461

This is a variation of subset sum problem (with 2 dimensions, adults and kids), where your sum is the number of persons and children and the the elements are the rooms.

It seems though, your problem is fairly small (you won't have hundreds of room types, only a few of them, and each traveler orders rooms for few people), so a brute force to show all possibilities is a one possibility to solve the problem.

The idea will be to generate ALL such rooms in recursive way, and before showing a possibility to the customer - check it meets the demands.
The recursive algorithm will first "guess" if you want to use the current room type, and for both options - recurse for a smaller problem.

Java-like Pseudo code:

private boolean matches(List<Room> rooms, int adults, int children) { 
    //check if the current list of rooms satisfies the demands
}
private int numPersons(List<Room> rooms) { 
    int res = 0;
    for (Room r : rooms) { 
        res += r.adults;
        res += r.children;
    }
    return res;
}

//wrapper function
public void generateAllPossibilities(List<Room> roomTypes, int adults, int children) { 
          generateAllPossibilities(roomTypes, adults, children, new ArrayList<>(), 0);
}

private void generateAllPossibilities(List<Room> roomTypes, int adults, int children, List<Room> soFar, int i) { 
    //check stop clauses, a "good" match, or out of bound:
    if (matches(soFar,adults,children)) {
         showOption(soFar); //succesful stop clause
         return;
    }
    if (i == roomTypes.size() || numPersons(rooms) > adults + children) {  
         return; //failing stop clause
    }
    //"guess" to add the current room type:
    soFar.add(roomTypes.get(i));
    //recurse with that guess:
    generateAllPossibilities(roomTypes, adults, children, soFar, i);
    //"guess" not to add the current room type
    soFar.remove(soFar.size()-1));
    generateAllPossibilities(roomTypes, adults, children, soFar, i+1);
}

Upvotes: 2

Related Questions