Find the maximum height they can do while standing on top of each other?

The weights of Russian men and their strengths (the maximum weight they can carry) are given. The height of all is the same and given. Find the maximum height they can do while standing on top of each other? This means that you have to place them by taking the maximum number of men from them so that no one weighs more than their strength.

This question bugs me. At first I thought using greedy, first taking the person with maximum strength, but he doesn't give the correct answer. Then I tried to solve it like a knapsack, which is also wrong. I cannot think of an efficient algorithm. Can anyone please help?

+3


source to share


1 answer


First of all sorry for my english :)

Here is one way you can think of as a way to solve the problem.

It's good if you can assume that each floor absorbs all the weight in a single form (I mean there are no restrictions such as "one person can only carry the weight of two men" or something similar). We will start with a hypothetical structure with one person per floor, and with this structure, we will begin to test constraints and organize people.

We will check the lower floor (first floor) and we ask: can this floor handle the weight of all the upper floors?
If the answer is no, we remove one person from the top of the tower and we add them to that floor, and we check the weight status on that floor again. If the answer is yes, we move on to the next floor.



After that, we will have a structure that meets the requirements. And the C # code:

int amountOfMens    = n;
float weight        = w;
float strength      = s;
float height        = h;
int []mensInEachFloor;


public void MyAlg()
{
    mensInEachFloor = new int[ amountOfMens ]; // the max height that we can achieve is the max amount of mens.

    for(int i=0; i < mensInEachFloor.Length; i++ )
    {
        // we put one men on each floor, just to check if the highest heigth is achivable 
        mensInEachFloor[i] = 1;
    }

    // now we start to use our algorithm
    // for each floor:
    for(int i = 0; i < mensInEachFloor.Length; i++ )
    {
        // for each floor we will work on it until supports its designed weight 
        bool floorOk = false;

        while(! floorOk)
        {
            // we check if the weigth of all the higher floors can be supported by this level
            float weightToBeSupported       = TotalWeightOfHigherFloors(i+1);
            float weightThatCanBeSupported  = WeightHandledByFloor(i);

            if( weightToBeSupported > weightThatCanBeSupported )
            {
                // Remove one men from the top 
                RemoveOneManFromHighestFloor();
                // add one men to this floor to help with the weight
                AddOneManToFloor(i);
            }
            else
            {
                // we are ok on this floor :)
                floorOk = true;
            }
        }
    }

    Debug.Log("The total heigth of the tower is : " + GetTowerHeight() );
}

private float TotalWeightOfHigherFloors(int startingFloor)
{
    float totalWeight = 0;
    for(int i= startingFloor; i< mensInEachFloor.Length; i++ )
    {
        totalWeight += mensInEachFloor[i] * weight;
    }

    return totalWeight;
}

private float WeightHandledByFloor(int floor)
{
    return mensInEachFloor[floor] * strength;   
}

private void RemoveOneManFromHighestFloor()
{
    // we start to see from the top..
    for(int i = mensInEachFloor.Length - 1 ; i >= 0; i-- )
    {
        // if on this floor are one or more mens..
        if(mensInEachFloor[i] != 0)
        {
            // we remove from the floor
            mensInEachFloor[i] = mensInEachFloor[i] - 1;
            // and we are done
            break;
        }
    }
}

private void AddOneManToFloor(int floor)
{
    // Add one man to the selected floor
    mensInEachFloor[floor] = mensInEachFloor[floor] + 1;
}

private float GetTowerHeight()
{
    // We will count the number of floors with mens on it
    float amountOfFloors = 0;
    for(int i= 0; i< mensInEachFloor.Length; i++ )
    {
        // If there are more than zero mens
        if( mensInEachFloor[i] > 0 )
        {
            // it means that it is a valid floor
            amountOfFloors++;
        }
    }

    // number of floors times height
    return amountOfFloors * height;

}

      

Cheers!

0


source







All Articles