given an integer array V, V[i] being the value of the item at index i, and an integer array W, W[i] being the weight of the item at index i, and an integer maxW being the max weight you could carry.

The Catch: If you select an item at index i, the index of the next item you select can't have the same parity as i

Return: The maximum value you can get, if there are multiple solutions, return the solution with the least weight, if there are still multiple solutions, return a solution where the first item selected has the least index. Followed by the indexes of the items that are selected.

EXAMPLES Example 1: W = [30, 10, 20, 20, 10, 10] V = [120, 60, 200, 50, 20, 10] maxW = 45 answer:

270 1 2 5 note: 280 1 2 4 is a not solution because the item at index 2 and 4 can't be selected right after another.

Example 2: W = [10, 20, 20, 30] V = [60, 110, 70, 120] maxW = 40 answer:

180 0 3 note: 180 1 2 is also an answer but there is an answer that starts with a lower index

Example 3: W = [10, 19, 20, 30] V = [60, 110, 70, 120] maxW = 40 answer:

180 1 2 note: 180 0 3 is also an answer but it costs more

ATTEMPTS Started this as a regular knapsack problem, but with the parity constraint, we can only select an item if the last item's index has a different parity. But what if it is the first item selected? we need extra complexity to keep track of that too. Maybe keep track of the selected items along the way with an array, but the memory needed for that is huge!

QUESTION Is this even still a knapsack problem, it has been altered so much, if so, what is an efficient solution?