Varastossa on n laatikkoa, joilla jokaisella on tietty paino. Montako laatikkoa voit pakata enintään autoon, kun auton lastin maksimipaino on x?
Algoritmin aikavaativuuden tulee olla O(n \log n).
Toteuta tiedostoon packbox.py funktio solve, joka ilmoittaa, montako laatikkoa voit pakata enintään.
def solve(t, x):
# TODO
if __name__ == "__main__":
print(solve([1, 1, 1, 1], 2)) # 2
print(solve([2, 5, 3, 2, 8, 7], 10)) # 3
print(solve([2, 3, 4, 5], 1)) # 0
print(solve([2, 3, 4, 5], 10**9)) # 4
print(solve([10**9, 1, 10**9], 10**6)) # 1
Selitys: Ensimmäisessä esimerkissä voit pakata mitkä tahansa kaksi laatikkoa. Toisessa esimerkissä voit pakata kolme laatikkoa, esimerkiksi listan kolme ensimmäistä laatikkoa, jotka painavat yhteensä 10. Kolmannessa esimerkissä et voi pakata mitään laatikkoa, koska jokainen painaa enemmän kuin 1.