Pack Objects with Greedy Algorithm: Is It Right?

[evinda]

Hello! (Wave)

At a relocation we have $N$ objects with the same weight that we want to pack in boxes. We have at our disposal boxes of capacity 1,2,5,10 and 20 objects (so many that we want from each size). In order the objects not to move at the transfer, each box should be completely full. I want to write and analyze a greedy algorithm that computes the minimum number of boxes needed to pack the objects.

I have thought of the following algorithm:

boxes=0
remaining=N
while (remaining>=20) {
         boxes=boxes+1
         remaining=remaining-20
}
while (remaining>=10) {
         boxes=boxes+1
         remaining=remaining-10
}
while (remaining>=5) {
         boxes=boxes+1
         remaining=remaining-5
}
while (remaining>=2) {
         boxes=boxes+1
         remaining=remaining-2
}
while (remaining>=1) {
         boxes=boxes+1
         remaining=remaining-1
}
return remaining

Is my algorithm right? Could something be improved?

The algorithm is greedy, isn't it? (Thinking)

 

[I like Serena]

Is my algorithm right?

Hey evinda!

You are returning [M]remaining[/M] as the result of the algorithm.
But that one will always be zero, won't it?
I don't think that is the result of the algorithm. (Worried)

The algorithm is greedy, isn't it?

Yep. At every step you select the biggest option. And that makes it greedy. (Nod)

Could something be improved?

We might optimize it a bit and eliminate the while-loops.
Instead of:

while (remaining>=20) {
         boxes=boxes+1
         remaining=remaining-20
}

we can do:

boxes += remaining / 20
remaining -= remaining % 20

can't we?
It reduces the complexity of the algorithm. (Nerd)

 

[evinda]

Hey evinda!

You are returning [M]remaining[/M] as the result of the algorithm.
But that one will always be zero, won't it?
I don't think that is the result of the algorithm. (Worried)

Yes, right... [m]boxes[/m] should be the result of the algorithm... (Tmi)

Yep. At every step you select the biggest option. And that makes it greedy. (Nod)

I see! (Blush)

We might optimize it a bit and eliminate the while-loops.
Instead of:

while (remaining>=20) {
         boxes=boxes+1
         remaining=remaining-20
}

we can do:

boxes += remaining / 20
remaining -= remaining % 20

can't we?
It reduces the complexity of the algorithm. (Nerd)

Shouldn't the command of remaining be remaining=remaining%20 ? I have applied it at an example... (Blush)So the algorithm is the following, right?

boxes=0
remaining=N
boxes+=remaining/20
remaining=remaining%20
boxes+=remaining/10
remaining=remaining%10
boxes+=remaining/5
remaining=remaining%5
boxes+=remaining/2
remaining=remaining%2
boxes+=remaining
return boxes

The complexity of the algorithm is the complexity of the operations of division and modulus done.

The division and computation of modulus of $a$ and $b$, where $a,b$ arbitrary, takes $O(\log{a} \cdot \log{b})$ time, doesn't it?

So the complexity of the algorithm is $O(\log{20} \cdot \log{N})=O(\log{N})$, right?Or is something of the above wrong? (Thinking)

 

[I like Serena]

Shouldn't the command of remaining be remaining=remaining%20 ? I have applied it at an example...

It is. (Tmi)

So the algorithm is the following, right?

Yep. (Nod)

The complexity of the algorithm is the complexity of the operations of division and modulus done.

The division and computation of modulus of $a$ and $b$, where $a,b$ arbitrary, takes $O(\log{a} \cdot \log{b})$ time, doesn't it?

So the complexity of the algorithm is $O(\log{20} \cdot \log{N})=O(\log{N})$, right?

It depends on the complexity of division and modulus.
Rather than making the assumption that they are $\log(a)\cdot\log(b)$, I propose to simply count the number of operations and leave it at that.
Then the complexity is:
$$4 \operatorname{divisions} + 4 \operatorname{moduli} + 5 \operatorname{additions} = O(1)$$
(Thinking)

Btw, we can simplify it a little more with:

    int boxes = 0;
    for (int b : {20, 10, 5, 2, 1}) {
        boxes += N / b;
        N %= b;
    }
    return boxes;

That doesn't impact the complexity though. (Nerd)

 

[evinda]

It depends on the complexity of division and modulus.
Rather than making the assumption that they are $\log(a)\cdot\log(b)$, I propose to simply count the number of operations and leave it at that.
Then the complexity is:
$$4 \operatorname{divisions} + 4 \operatorname{moduli} + 5 \operatorname{additions} = O(1)$$
(Thinking)

Btw, we can simplify it a little more with:

    int boxes = 0;
    for (int b : {20, 10, 5, 2, 1}) {
        boxes += N / b;
        N %= b;
    }
    return boxes;

That doesn't impact the complexity though. (Nerd)

I see... Thanks lot! (Blush)