Wildlife Survey Time Frontier

Max value per exact total weight from arrays, at most one item per group

MediumDynamic ProgrammingMultiple-Choice Knapsack

A wildlife research team has a catalog of optional survey sessions. Session i takes duration[i] hours, provides value[i] research points, and studies habitat habitat[i].

The team may select any subset of sessions, but it may select at most one session from each habitat. Each session can be selected only once. Session durations and research points add together, and there are no other scheduling restrictions.

Return an integer list best of length budget + 1. For every t from 0 through budget:

  • best[t] is the maximum total research points obtainable with sessions whose total duration is exactly t.
  • If no valid selection has total duration exactly t, set best[t] to -1.

Selecting no sessions is allowed, so best[0] is always 0. Habitat identifiers are labels; their numeric order has no significance.

Examples

Example 1

Input: duration = [2,4,3], value = [5,11,7], habitat = [8,8,2], budget = 7
Output: [0,-1,5,7,11,12,-1,18]

The first two sessions study the same habitat, so they cannot be combined. The third session may be combined with either of them. In particular, an exact duration of five hours can be achieved by choosing the first and third sessions.

Example 2

Input: duration = [2,3], value = [4,6], habitat = [5,5], budget = 5
Output: [0,-1,4,6,-1,-1]

Both sessions study the same habitat. Although their durations add to five hours, selecting both is forbidden, so that duration is unreachable.

Example 3

Input: duration = [], value = [], habitat = [], budget = 3
Output: [0,-1,-1,-1]

There are no sessions. Only the empty selection is possible, making every positive duration unreachable.

Constraints

  • 0 <= duration.length <= 300
  • value.length == habitat.length == duration.length
  • 1 <= duration[i] <= 6000
  • 0 <= value[i] <= 1000000
  • 0 <= habitat[i] <= 1000000000
  • 0 <= budget <= 6000

The intended solution takes O((n + 1)(budget + 1)) time and O(n + budget) auxiliary space, where n is the number of sessions. Research points are nonnegative, so -1 is an unambiguous unreachable marker.

Hints

Show hint 1

Group the sessions by habitat. After processing some habitats, track the best score for each exact duration.

Show hint 2

When processing one habitat, compute all choices from the state before that habitat was processed. This prevents selecting two sessions from the same habitat.

Follow-up questions

What an interviewer might ask once you have a working solution.

  • How would you change the transitions if exactly one session from every habitat were required?
  • How could you reconstruct one optimal selection for a requested reachable duration?

Practice this with an AI interviewer

Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.

Start this problem