Gift Knapsack Problem

Gift Knapsack Problem

Santa is preparing his sleigh for the holiday season and has a number of gifts with different weights and associated "happiness" values. Due to weight limitations of his sleigh, Santa can only carry gifts up to a certain total weight. Your task is to help Santa determine the maximum total happiness value he can achieve by selecting a subset of gifts without exceeding the weight capacity.

Problem Details

• You are given two arrays: one representing the weights of the gifts and the other representing the corresponding happiness values of these gifts.
• You are also given an integer capacity representing the maximum total weight that can be carried.
• Your goal is to implement a function that returns the maximum total happiness value possible by picking a subset of the gifts such that their total weight does not exceed the capacity.

This problem is a variation of the classic 0/1 Knapsack problem, which can be solved using dynamic programming.

Input / Output Example

For example, given:

• weights = [2, 3, 4, 5]
• values = [3, 4, 5, 6]
• capacity = 5

The maximum total happiness value is 7 (by picking the gifts with weight 2 and 3).

Starter Code

Use the starter code for your preferred language to begin your solution.

Happy coding and have a joyful holiday season!