- #1

evinda

Gold Member

MHB

- 3,836

- 0

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:

Code:

```
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
```

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