takidwad's blog

How to Solve this problem!! please help.
By takidwad, history, 10 months ago, In English

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?

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by takidwad (previous revision, new revision, compare).

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What are the constraints? One solution could be to Fix every element of array from left as starting element and perform knapsack on remaining [l+1, n] range with state being dp[i][last_parity] and take max among all.

→ Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    The constraints is

    • Maximum money * weight.size <= 10e5
    • itemi represent by the index
    • wi represent pi(wi has point of pi)
    • result priority: maximum point -> smaller money to spend -> smaller lexicograph
    • We can only pick item only once
    • We pick item in ascending order
    • for example, we given
    • w [10,20,19,30]
    • p [60,110,70,120]
    • capacity 40
    • Result : 180 2 3
    • Explanation: The maximum we can get is 180, because we can only pick an item that the parity is different from item that we picked exactly before. We can see, we can get 180 from picking item 1 4 or 2 3, because 2 3 has less money to spend, the result is 180 2 3
    • Another example
    • w [10,10,20,10,10]
    • p [10,10,20,10,10]
    • capacity 30
    • Result: 30 1 2 5
    • Explanation: The maximum point we can get is 30, we ca get 30 from picking item 1 2 5, 1 4 5. We can see both has the same amount money to spend. We pick items that has the smaller lexicograph, because 1 2 5 is smaller than 1 4 5, thus the result is 30 1 2 5
    → Reply