Knapsack Problem
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:
- 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.
- 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
2and3(happiness values3and4) 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!
Inputs
Arg 1:
[[2,3],[1,2],[3,4],[2,2]]Arg 2:
5Expected Output
7Actual Output