Algorithm of 12608 - Garbage Collection

Problem Description Link
Algorithm

This is a simple problem this problem you can solve easily . To solve this problem you must remember 3 conditions.

Garbage truck is collecting garbage on its route starting at the dump and collecting garbage from pick up points in order (closest first). Garbage truck returns to the dump and empties its contents if it either

1. is full or
2. cannot load the garbage at the current point because it will put the load over the weight limit (the truck driver has no way of knowing the weight of the garbage at a particular pick up point until the truck reaches that point) or
3. there are no more pick up points left

when you return to dump you need 2 time distance.

For example

1

3 3

1 2

2 2

3 1

In this example the truck can load 3 ton and 3 points .

First step :

Go to point 1 take garbage  then go to point 2 but don’t take garbage because of overload weight so go back to dump and empties its contents . distance for one time=2

                                                                                                    

Second step:

Again go to point 2 and take garbage then go to point 3 and take garbage because no over load

So distance for one way for second stapes= 3 and return to dump

 

So total one way distance for all stapes= 2+3 =5

Each time need back to dump  so total distance= 5*2 =10

So 10 is final result.

e.g. this is not allowed: get a portion of garbage at some point until truck is full and come back for the rest and same operation perform when truck is full.