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