Skip to content

Instantly share code, notes, and snippets.

@nhahtdh
Created May 4, 2013 19:18
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save nhahtdh/5518441 to your computer and use it in GitHub Desktop.
Save nhahtdh/5518441 to your computer and use it in GitHub Desktop.
// Original code by SergeyS
// http://stackoverflow.com/a/16377911/1400768
class Test16377079 {
static int[] GetAssignments(int[] studentsPerLetter, int[] rooms)
{
int numberOfRooms = rooms.length;
int numberOfLetters = studentsPerLetter.length;
int roomSets = 1 << numberOfRooms; // 2 ^ (number of rooms)
int map[][] = new int[numberOfLetters + 1][roomSets];
for (int i = 0; i <= numberOfLetters; i++)
for (int j = 0; j < roomSets; j++)
map[i][j] = -2;
map[0][0] = -1; // starting condition
for (int i = 0; i < numberOfLetters; i++)
for (int j = 0; j < roomSets; j++)
if (map[i][j] > -2)
{
for (int k = 0; k < numberOfRooms; k++)
if ((j & (1 << k)) == 0)
{
// this room is empty yet.
int roomCapacity = rooms[k];
int t = i;
for (; t < numberOfLetters && roomCapacity >= studentsPerLetter[t]; t++)
roomCapacity -= studentsPerLetter[t];
// marking next state as good, also specifying index of just occupied room
// - it will help to construct solution backwards.
map[t][j | (1 << k)] = k;
}
}
// Constructing solution.
int[] res = new int[numberOfLetters];
int lastIndex = numberOfLetters - 1;
for (int j = 0; j < roomSets; j++)
{
int roomMask = j;
while (map[lastIndex + 1][roomMask] > -1)
{
int lastRoom = map[lastIndex + 1][roomMask];
int roomCapacity = rooms[lastRoom];
for (; lastIndex >= 0 && roomCapacity >= studentsPerLetter[lastIndex]; lastIndex--)
{
res[lastIndex] = lastRoom;
roomCapacity -= studentsPerLetter[lastIndex];
}
roomMask ^= 1 << lastRoom; // Remove last room from set.
j = roomSets; // Over outer loop.
}
}
return lastIndex > -1 ? null : res;
}
public static void main(String args[]) {
int[] studentsPerLetter = { 50, 100, 200, 120 };
int[] rooms = { 320, 200 };
int[] ans = GetAssignments(studentsPerLetter, rooms);
System.out.println(java.util.Arrays.toString(ans));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment