Can anyone help me to answer this question
Difference between en1 and en2, changed 2 character(s)
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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English takidwad 2023-09-30 11:46:52 52
en2 English takidwad 2023-09-28 14:01:43 2 Tiny change: 'is huge!\nQUESTION' -> 'is huge!\n\nQUESTION'
en1 English takidwad 2023-09-28 13:59:14 1679 Initial revision (published)