Maximum Value from Unit-Weight Items with Limited Copies Under a Capacity

You are packing items into a bag that can hold a total weight of at most capacity. There are n item types. Every copy of item type i weighs exactly 1 and is worth values[i], and counts[i] identical copies of it are available. This is a bounded knapsack in which every item has the same unit weight.

Return the maximum total value you can pack.

Function Signature

def max_packed_value(values: list[int], counts: list[int], capacity: int) -> int:

values[i] and counts[i] describe item type i.

Rules

• Choose a whole number of copies x[i] of each item type with 0 <= x[i] <= counts[i], so that the total weight x[0] + x[1] + ... + x[n - 1] is at most capacity.
• The total value is the sum of x[i] * values[i] over all item types. Return the largest achievable total value.
• The bag does not have to be full. If nothing is packed, the total value is 0.

Constraints

• 1 <= len(values) == len(counts) <= 10^5
• 0 <= values[i] <= 10^6
• 1 <= counts[i] <= 10^9
• 0 <= capacity <= 10^9
• The total number of copies, sum(counts), can reach 10^14, and the answer can reach 10^15. Both exceed 2^31 - 1, so use 64-bit integers in languages with fixed-width integer types; both stay below 2^53.

Examples

Example 1

Input: values = [6, 10, 3], counts = [2, 1, 5], capacity = 4
Output: 25

The best choice packs the single copy worth 10, both copies worth 6 and one copy worth 3: 10 + 6 + 6 + 3 = 25, using all 4 units of capacity.

Example 2

Input: values = [4, 7], counts = [3, 2], capacity = 10
Output: 26

Only 5 copies exist, fewer than the capacity of 10, so all of them fit: 3 × 4 + 2 × 7 = 26.

Example 3

Input: values = [5, 0, 9], counts = [1000000000, 3, 1], capacity = 1000000000
Output: 5000000004

Packing the copy worth 9 and 999,999,999 copies worth 5 gives 9 + 4,999,999,995 = 5,000,000,004, which does not fit in a 32-bit signed integer. The copies worth 0 add nothing.