Suppose you work for a major package shipping company, FedUP, as in the previous

Question

Suppose you work for a major package shipping company, FedUP, as in the previous exercise, but suppose there is a new law that requires every truck to carry no more than M pounds, even if it has room for more boxes. Now the optimization problem is to use the fewest number of trucks possible to carry the n boxes across the country such that each truck is carrying at most M pounds. Describe a simple greedy algorithm for assigning boxes to trucks and show that your algorithm uses a number of trucks that is within a factor of 2 of the optimal number of trucks. You may assume that no box weighs more than M pounds.

Explanation / Answer

Hi,

Find the steps of Algorithm below:-

1.Input number of boxes N and weight of each box W(1), W(2)......W(n)

2. Input the max weight allowed to carry by every truck M

3. Put the sum in temporary variable temp = W(1) + W(2) +.....W(n)

4. Check if sum is exactly divisible by maximum weight to be carried by truck 'M'

if(temp%M)==0

Then assign the result of diviliding temp and maximum weight to be carried by truck to res

res = temp/M

If sum is not exactly divisible by maximum weight to be carried by truck i.e. temp%M != 0

then

res = temp/M +1

5. end

Let's simulate the algo with the help of example:-

Let's suppose we have 3 boxes of weights as given:- w1= 200, w2 = 400, w3= 400 and maximum weight to be carried = 500

temp = 200+400+400 =1000

1000%500 == 0 --> condition satisfied

res = 1000/500 =2

Let's take one more example:-

w1= 800, w2 = 700, w3= 600 and capacity = 1000

temp = 800+700+600 =2100

2100%1000 != 0 --> condition not satisfied

res = 2100/1000 +1 =2 +1 =3

Hope this will help you and you have understood. Thanks...Do give this a thumbs up!!!:)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.