← Questions
Best value from unit-weight items with limited copies
0
I was asked this
No reports yet. Sign in to say where you were asked it.
A bag holds at most capacity units of weight. There are n kinds of item; every copy of kind i weighs 1 and is worth values[i], and there are counts[i] copies of it. Return the most value you can pack.
def max_packed_value(values: list[int], counts: list[int], capacity: int) -> int: ...
n is up to 10^5 and capacity and counts are up to 10^9, so the textbook knapsack table is out of the question. Explain why the unit weights make a simpler approach correct, and watch for totals that overflow 32 bits.
No official answer yet. Write yours on the right and run it.
Nothing published yet.
Write and test your solution herePython in your browser, the question's tests level by level, saved for you.Sign in to start coding
