Gegeven een lijst van \(n\) objecten. Deze objecten hebben elk een bepaald volume. Men wenst deze objecten te vervoeren met vrachtwagens, maar wel zo dat er zo weinig mogelijk vrachtwagens worden gebruikt. Alle vrachtwagens hebben eenzelfde capaciteit. De objecten moeten dus op een slimme manier worden ingeladen in de vrachtwagens zodanig dat het aantal te gebruiken vrachtwagens zo laag mogelijk is.

Ontwerp en implementeer een gretig algoritme dat een reeks gegeven objecten verdeelt over een zo klein mogelijk aantal vrachtwagens, waarbij het totale volume van de objecten in een vrachtwagen diens capaciteit niet mag overschrijden.

Opgave

Schrijf een Python-functie pack(items: list, d: int). Deze Python-functie neemt een lijst die de volumes van de items bevat en een maximum capaciteit. Als output geeft deze functie een lijst met (zo weinig mogelijk) opgevulde vrachtwagens terug.

Voorbeelden

>>> pack([12, 12, 12], 12)
[[12], [12], [12]]
>>> pack([4, 3, 4, 6, 2, 4, 5, 1, 1, 2, 2, 2, 4], 10)
[[6, 4], [5, 4, 1], [4, 4, 2], [3, 2, 2, 2, 1]]
>>> pack([1, 1, 1, 1, 8, 7, 6, 6], 9)
[[8, 1], [7, 1, 1], [6, 1], [6]]