Treasure Room: Maximize Value with Weight-Constrained Knapsack Variant

Question

## Problem

You enter a treasure room containing `n` items. Each item has a `weight`, a `value`, and a `fragility` rating. You can carry at most `W` total weight. Additionally, if you carry any fragile item (fragility > 0), the total fragility score of all chosen items must not exceed `F`.

Return the maximum value you can carry out.

```python
def max_treasure(
    items: list[tuple[int, int, int]],  # (weight, value, fragility)
    W: int,
    F: int
) -> int:
    pass
```

## Example

```
Input:
items = [(3, 10, 0), (2, 7, 3), (4, 15, 2), (1, 4, 5)]
W = 6, F = 4

Output: 22
# Take item 0 (w=3,v=10,f=0) + item 2 (w=4,v=15,f=2) -- exceeds W
# Take item 1 (w=2,v=7,f=3) + item 2 (w=4,v=15,f=2): total w=6, f=5 > F
# Take item 0 + item 1: w=5, f=3 <= F, value=17
# Take item 0 + item 3: w=4, f=5 > F
# Optimal: item 2 + item 3: w=5, f=7 > F
# Answer: 17 (item 0 + item 1)
Output: 17
```

## Follow-ups

1. How does adding the fragility constraint change the DP state space?
2. Can you solve this greedily? If not, why?
3. What if items can be partially taken (fractional knapsack with fragility)?

Treasure Room: Maximize Value with Weight-Constrained Knapsack Variant

Question Details

Full Details

Topics

More from Karat