Given an array of integers (with at least two elements), I need to choose at least one element of each adjacent pair of elements in the array in a way that costs me the least. Then, return the cost and elements chosen.
For example,
[50, 30, 40, 60, 10, 30, 10]
We choose 30 for the pair (50, 30), and for the pair (30, 40). Then we choose 40 for the pair (40, 60) and 10 for the pairs (60, 10), (10, 30). Lastly, 10 for the pair (30, 10). So we got 30 + 40 + 10 + 10 = 90.
Another example,
[60, 100, 70]
There are two possible selections: [60, 70] or [100]. But, the optimal solution would be [100] for a total of 100, which is less than 60 + 70. So, the algorithm should choose 100.
My issue is that I only succeeded in making a code that returns the lowest cost without saving the elements used.
My Code in Python
arr = [50, 30, 40, 60, 10, 30, 10]
min_sum = [0] * len(arr)
min_sum[0] = arr[0]
min_sum[1] = arr[1]
for i in range(2, len(arr)):
choice1 = min_sum[i-1] + arr[i]
choice2 = min_sum[i-2] + arr[i]
min_sum[i] = min(choice1, choice2)
res = min(min_sum[-1], min_sum[-2])
print(res)
Calling cost(i) the cost of the optimal solution when considering the array up to element i included only, there is a simple recurrence formula for this problem:
cost(i) = min(
arr[i] + cost(i-1),
arr[i-1] + cost(i-2),
)
For instance, the cost for array [50, 30, 40, 60, 10, 30, 10] is the minimum of
10 + cost for [50, 30, 40, 60, 10, 30]
30 + cost for [50, 30, 40, 60, 10]
The base cases for this recurrence are:
cost(0) = 0
cost(1) = 0
cost(2) = min(arr[0],arr[1])
This recurrence relation leads to a simple iterative code:
def cost(a):
if len(a) <= 1:
return 0
elif len(a) == 2:
return min(a)
cost_iminus2 = 0
cost_iminus1 = min(a[:2])
for i in range(2,len(a)):
cost_i = min(
arr[i] + cost_iminus1,
arr[i-1] + cost_iminus2,
)
cost_iminus2, cost_iminus1 = cost_iminus1, cost_i
return cost_i
You can easily amend this code to also remember which elements were used in the sum:
def selection(a):
if len(a) < 2:
return 0, []
elif len(a) == 2:
return min(a), [min(a)]
cost_iminus2, selection_iminus2 = 0, []
cost_iminus1, selection_iminus1 = min(a[:2]), [min(a[:2])]
for i in range(2,len(a)):
cost_i = min(
a[i] + cost_iminus1,
a[i-1] + cost_iminus2,
)
if cost_i == a[i] + cost_iminus1:
selection_i = [*selection_iminus1, a[i]] # need to copy
elif cost_i == a[i-1] + cost_iminus2:
selection_i = selection_iminus2 # no need to copy
selection_i.append(a[i-1])
else:
raise ValueError("unreachable branch")
cost_iminus2, cost_iminus1 = cost_iminus1, cost_i
selection_iminus2, selection_iminus1 = selection_iminus1, selection_i
return cost_i, selection_i
Output:
>>> selection([50, 30, 40, 60, 10, 30, 10])
(90, [30, 40, 10, 10])
>>> selection([60,100,70])
(100, [100])