Created
May 4, 2013 19:18
-
-
Save nhahtdh/5518441 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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