Treasure Hunt - Knapsack Problem

You are given a set of treasures, each with a weight and a value. The task is to determine the maximum total value of treasures that can be carried without exceeding the maximum weight capacity.

Let \( N \) be the number of treasures, \( W = [w_1, w_2, \dots, w_N] \) be the list of weights, \( V = [v_1, v_2, \dots, v_N] \) be the list of values, and \( C \) be the capacity of the knapsack. You are to maximize the total value while ensuring that the sum of the weights does not exceed \( C \).

The standard dynamic programming solution iterates through the items and computes the maximum possible value for each intermediate capacity.

inputFormat

The first line contains two integers \( N \) and \( C \) separated by a space, where \( N \) is the number of treasures and \( C \) is the maximum weight capacity of the knapsack.

If \( N > 0 \), the second line contains \( N \) space-separated integers representing the weights \( W \) of the treasures.

If \( N > 0 \), the third line contains \( N \) space-separated integers representing the values \( V \) of the treasures.

If \( N = 0 \), the second and third lines will be empty.

outputFormat

Output a single integer, which is the maximum total value of the treasures that can be carried without exceeding the weight capacity.

4 5
2 3 4 5
3 4 5 6

7