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?
↵
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?
