Laatikot

Tehtäväsi on pakata annetut tuotteet laatikoihin. Tiedossasi on kunkin tuotteen paino sekä suurin sallittu tuotteiden yhteispaino laatikossa. Montako laatikkoa tarvitset vähintään?

Esimerkiksi jos tuotteiden painot ovat [2,3,3,5] ja laatikon maksimipaino on 7, tarvitaan vähintään kaksi laatikkoa:

• Laatikko 1: tuotteiden painot 2 ja 5 (yhteispaino 7)
• Laatikko 2: tuotteiden painot 3 ja 3 (yhteispaino 6)

Toteuta tiedostoon boxweight.py funktio min_count, jolle annetaan tuotteiden painot sekä laatikon maksimipaino. Funktion tulee palauttaa pienin laatikoiden määrä. Jos tehtävä on mahdoton, funktion tulee palauttaa -1.

Voit olettaa, että tuotteiden määrä on välillä 1 \dots 8. Funktion tulee toimia tehokkaasti kaikissa tällaisissa tapauksissa.

def min_count(weights, max_weight):
    # TODO

if __name__ == "__main__":
    print(min_count([2, 3, 3, 5], 7)) # 2
    print(min_count([2, 3, 3, 5], 6)) # 3
    print(min_count([2, 3, 3, 5], 5)) # 3
    print(min_count([2, 3, 3, 5], 4)) # -1

    print(min_count([], 1)) # 0
    print(min_count([1], 1)) # 1
    print(min_count([1, 1, 1, 1], 1)) # 4
    print(min_count([1, 1, 1, 1], 4)) # 1

    print(min_count([3, 4, 1, 2, 3, 3, 5, 9], 10)) # 3