Knapsack Problem

Advanced

Knapsack Problem: A Fun Packing Challenge!

Imagine you are going on a treasure hunt and you have a magical backpack (a knapsack) that can carry only up to a certain weight. You have a list of shiny treasures, each with a specific weight and a value of happiness it brings. Your goal is to pack the backpack in such a way that it carries the most happiness, without tipping over from being too heavy!

Your task is to write a function called knapsack that takes in two arguments:

  1. A list of tuples, each tuple containing the weight and happiness value of a treasure. For example, [(2, 3), (1, 2), (3, 4), (2, 2)] means there are four treasures:
    • First treasure weighs 2 and has a happiness value of 3,
    • Second treasure weighs 1 and has a happiness value of 2, and so on.
  2. An integer representing the maximum weight that your knapsack can hold.

The function should return an integer representing the maximum happiness value possible with the given weight constraint.

Example:

print(knapsack([(2, 3), (1, 2), (3, 4), (2, 2)], 5)) # Output: 7

Explanation:

  • You can pick treasures with weights 2 and 3 (happiness values 3 and 4) to get the maximum happiness of 7, which is under the weight constraint.

Here are more examples:

print(knapsack([(1, 1), (2, 2), (3, 5), (4, 6)], 3)) # Output: 5 print(knapsack([(1, 10), (2, 5), (3, 8), (4, 9)], 4)) # Output: 18

Can you help your magical backpack achieve maximum happiness without exceeding the weight limit? Have fun with this classic problem-solving challenge!

Geek
Inputs

Arg 1:

[[2,3],[1,2],[3,4],[2,2]]

Arg 2:

5
Expected Output
7
Actual Output