Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

Greedy Algorithm Problem: Blocks and Containers

p1niup1niu Posts: 1Member
Hello everyone! I have the following problem and I need to find a greedy algorithm which will solve it:

There are N numbered containers (1...N). In the containers, there are blocks in K-colors, but in all containers there is no more than N blocks of the given color.
Capacity of the i-th container is Pi (it can hold maximum of Pi blocks). Find an algorithm that will rearrange the blocks so that in each container there is at most one block each color. In one step, you are allowed to move only one block from the container to its neighbour (from i-th container, you can move a block to either (i+1)-th or (i-1)-th container, you can also move blocks between 1'st and n-th container).

I'd really appreciate any help. Can anyone give me any clues how to solve this problem using a greedy algorithm?
Many thanks.

Comments

  • XLoomXLoom Posts: 129Member
    I would do something like this: search for a container that has blocks that require moving out, try to move the block to left or right, repeat.

    Here is a pseudo-something-code for it. I didn't bother to write all of the functions, these are very simple anyway.
    [code]
    Container {
    int maximumBlocks;
    Block blocks[];
    };

    Container containers[]; // Assume circular array of containers

    int current=0;
    int minimumMovesRequired=1; // Minimum known number of moves required

    // Loop until we know that there are no more moves required -
    // in other words until everything is place
    while(minimumMovesRequired>0) {

    // Check through all containers
    for(int i=0; i<containers.count(); i++) {
    Block blocks[]=containers[i].blocks;

    // Check all blocks in current container
    for(int j=0; j<blocks.count(); j++) {
    Block block=blocks[j];

    // Find if this container has more than one block of this type
    if(containers[current].moreThanOneBlock(block)) {
    minimumMovesRequired++; // We know at least one container will be moved
    // so we won't know the state of all containers
    // and need to make next pass as well

    // Try to move the block to the right, no worries if it will fail
    // maybe it will work at later pass
    if(!containers[current+1].hasBlock(block)) {
    containers[current].blocks.remove(block);
    containers[current+1].blocks.push(block);
    }

    // Try to move the block to the left, ok if it will fail
    else if(!containers[current-1].hasBlock(block)) {
    containers[current].blocks.remove(block);
    containers[current-1].blocks.push(block);
    }
    }
    }
    }
    }
    [/code]
Sign In or Register to comment.