Mission 14: "Activating the Core (Capstone)" ✨
Let's first define the recursive structure. The base case for our knapsack solver is when we have no more items to consider or no capacity left.
Mission Objective
Step 1 / 3
1. The Story: The Mission Briefing
"You've reached the Labyrinth's central core. To activate it, you must load it with a set of 'data artifacts.' Each artifact has a size and an 'energy value.' The core has a limited capacity. You must choose the combination of artifacts that provides the maximum total energy value without exceeding the core's capacity."
2. The Problem
The 0/1 Knapsack Problem.
3. The Task
You will first write a simple recursive solution and see it fail due to its terrible O(2n) efficiency. Then, you will upgrade it using Dynamic Programming, which improves the efficiency to O(N*W). Your optimized solution solves the problem instantly, activating the Labyrinth.
4. Concepts Applied
Practical implementation of Dynamic Programming.