pthiyana
BAN USERHere is my solution using DP. The idea is to keep track of all possible dish combinations that satisfy the previous N-1 people. Then we process the Nth person. We loop through the existing set of dish combinations, and if one is found that does not satisfy either of the Nth person's 2 preferences, we make a copy of that combination and add it to the end of the set. Then the failed combination in set is modified so that the Nth person's first choice is added to it. Then we modify the copy at the
end of the set so that the Nth person's second choice is added to it. (It may be possible that the newly added combination at the end of the set already is there, so in this case it is removed to avoid repeats.) Finally, we go through the set of good dish combinations and find the smallest one.
I used the bitset data type in C++ to make it easier to store the set of good dish combinations and two other test cases commented out.
Should be O(MN) time and O(N) space.
const int N = 6; // number of people
const int K = 7; // number of dishes
void checkAndAddToSets(bitset<K> *sets, bool* personPref, int numDishes, int& totalSets)
{
int choices[2];
int c(0);
// locate the 2 choices for the current person
for(int i=0; i<numDishes; i++)
if(personPref[i]==1)
choices[c++] = i;
int numInitialSets = totalSets;
// check if the choices are satisfied in the existing set.
// Only need to add sets if a combination doesn't contain either of the choices
for(int t=0; t<numInitialSets; t++)
if( sets[t][choices[0]]==0 && sets[t][choices[1]]==0 )
{
sets[totalSets] = sets[t]; // make a copy of the set that does not satisfy the
//person
sets[t][choices[0]] = 1; // add the first choice to the set
sets[totalSets++][choices[1]] = 1; // add the second choice to the copy set
// elminate adding combinations already there. Not totally necessary, saves
//space but costs time
for(int s=0; s<numInitialSets; s++)
if( sets[s]==sets[totalSets-1] )
{
totalSets--;
break;
}
}
}
//
void minDishesToFeedPeople()
{
bool Pref[N][K] = { {1, 0, 0, 0, 1, 0, 0},
{1, 0, 0, 0, 0, 1, 0},
{1, 0, 0, 0, 0, 0, 1},
{0, 1, 0, 0, 1, 0, 0},
{0, 0, 1, 0, 0, 1, 0},
{0, 0, 0, 1, 0, 0, 1}, };
//bool Pref[N][K] = { {1, 1, 0, 0, 0, 0, 0},
//{0, 1, 1, 0, 0, 0, 0},
//{0, 0, 1, 1, 0, 0, 0},
//{0, 0, 0, 1, 1, 0, 0},
//{0, 0, 0, 0, 1, 1, 0},
//{0, 0, 0, 0, 0, 1, 1}, };
//bool Pref[N][K] = { {1, 0, 0, 0, 0, 0, 1},
//{0, 1, 0, 0, 0, 1, 0},
//{0, 0, 1, 0, 1, 0, 0},
//{0, 0, 0, 1, 1, 0, 0},
//{0, 0, 1, 0, 0, 1, 0},
//{0, 0, 0, 1, 0, 1, 0}, };
int maxSets = 1000*N; // max is really 2^N?, but unlikely to need that many
int totalSets(0);
bitset<K>* sets = new bitset<K>[maxSets]; // stores set of good dish combinations
// initialize the first two sets from the first person
for(int i=0; i<K; i++)
if(Pref[0][i]==1)
sets[totalSets++][i] = 1;
// now loop through the remaining N-1 people and build up the possible sets that
// satisfy everyone
for(int n=1; n<N; n++)
checkAndAddToSets(sets, Pref[n], K, totalSets);
// Now find the smallest set
int minSetIndx(0);
int minDishes = sets[0].count();
for(int i=1; i<totalSets; i++)
if(sets[i].count()<minDishes)
{
minDishes = sets[i].count();
minSetIndx = i;
}
for(int j=0; j<K; j++)
cout << sets[minSetIndx][j] << " ";
cout << endl;
delete []sets;
}
Here is my solution. It is a relaxation technique, that swaps values until we reach a minimal difference between the sums of the two split arrays. The steps are as follows:
1) Input is an array of size N.
2) Initialize the two arrays a(size n) and b(size m) by simply splitting the input array. n+m=N.
2) Create a 2D difference table of size n X m, where difference[i,j] = a[i]-b[j];
3) Compute the sums a and b, and compute the error = sum(a) - sum(b);
4) Now we do the relaxation iterations, where we swap values of a and b until the error between their sums reaches a minimum. We find the indices to swap by looking at the difference table. We want the value/indices in the difference table closest to 0.5*error. We need half because we want to increase the value of one array by 0.5*error, and decrease the value of the other by 0.5*error.
5) After swapping the values, we must update the difference table, but only have to update one row and one column, so it is fast.
6) The relaxation iterations stop when the error stops reducing.
This is O(N^3) in time theoretically, but seems to be O(N^2) in reality.
The relaxation seems to work fast.
Also O(N^2) in space, but around 0.25*N^2 space to be more accurate.
The code is in C++. Please try it and let me know if it works for you. I have tested in on random arrays of up to size 2000, and it works.
- pthiyana August 29, 2015