Pack the Backpack

Easy

A backpack can hold at most 5000 units of weight. You have some items in front of you, and weights[i] is the weight of item i. Return the largest number of items you can pack so that their total weight does not exceed 5000.

Example 1

weights=[1200, 300, 2500, 900, 1000] → 4

All five weigh 5900, which is too much. Without the heaviest one (2500) the rest weigh 3400, so four fit.

Example 2

weights=[1000, 1000, 1000, 1000, 1000] → 5

Exactly 5000 is still allowed, so everything goes in.

Example 3

weights=[999, 1000, 1000, 1000, 1000, 1000, 2] → 5

Constraints

1 ≤ len(weights) ≤ 10⁵
1 ≤ weights[i] ≤ 5000

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Sorting

Similar problems

Cake Slices for Guests Easy Strength of the Weaker Partner Easy Triangle From Sticks Easy Sign Flips for the Largest Sum Easy The Heavier Share of the Loot Easy

Input

weights=[1200, 300, 2500, 900, 1000]

Expected

Run checks the first 3 tests in your browser. Submit checks all 61 tests on the server, hidden ones included.