Maximum Value from Unit-Weight Items with Limited Copies Under a Capacity
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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
```python
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**
```text
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**
```text
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**
```text
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.
Overview: Find the maximum total value that fits in a bag whose capacity can reach one billion units, when every item weighs one unit and each item type has a value and a limited number of identical copies. Tests judging which knapsack techniques scale to huge capacities and copy counts, plus 64-bit arithmetic for large totals.
Read the full Google Software Engineer interview experience this question came from
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.
Implement `max_packed_value(values, counts, capacity)`, where `values[i]` and `counts[i]` describe item type `i`, and return the maximum total value you can pack.
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 as a single integer.
- 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 the answer is a 64-bit integer (`long` in Java, `long long` in C++); both stay below `2^53`, so JavaScript numbers hold them exactly.
Example 1:
Input: values = [6, 10, 3], counts = [2, 1, 5], capacity = 4
Output: 25
Explanation: Pack 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
Explanation: Only 5 copies exist, fewer than the capacity of 10, so all of them fit: 3 * 4 + 2 * 7 = 26.
Constraints
- 1 <= len(values) == len(counts) <= 10^5
- 0 <= values[i] <= 10^6
- 1 <= counts[i] <= 10^9
- 0 <= capacity <= 10^9
- sum(counts) can reach 10^14 and the answer can reach 10^15; both exceed 2^31 - 1 (use long in Java, long long in C++) and both stay below 2^53
Examples
Input: ([6, 10, 3], [2, 1, 5], 4)
Expected Output: 25
Explanation: Source Example 1: capacity runs out partway through the value-3 copies; 10 + 6 + 6 + 3 = 25.
Input: ([4, 7], [3, 2], 10)
Expected Output: 26
Explanation: Source Example 2: only 5 copies exist, below capacity 10, so all are packed: 3*4 + 2*7 = 26.
Hints
- Every copy weighs exactly 1, so packing any k copies uses exactly k units of capacity, whichever item types they come from.
- capacity can be 10^9 and sum(counts) can be 10^14, so anything that steps through capacity units or individual copies one at a time is too slow.
- The answer can reach 10^15, beyond the 32-bit range, so accumulate it in a 64-bit integer.