Implement the function computeBestPartition(l)

Question

In this problem, you are given a list of numbers l: [l[0], ..., l[n-1]]. Your goal is to partition this into two lists l1, l2 such that each element l[i] belongs to exactly one of l1, l2 and the difference between the sums of the two lists is minimized:

#min |sum(𝚕𝟷)−sum(𝚕𝟸)|

#where sum(𝚕)

#for a list 𝑙

#denotes the sum of the elements in a list.

Example:

l = [ 1, 5, 7, 8, 4, 6, 15]

Partition it as:

l1 = [1, 7, 15], l2 = [5, 8, 4, 6] 

Note that in this case sum(l1) = sum(l2) = 23. Thus, we have minimized the absolute difference to 0, which is the best possible.

Dynamic Programming Let 𝗆𝗂𝗇𝖠𝖻𝗌𝖣𝗂𝖿𝖿(𝑖,𝑠1,𝑠2) denote the minimum difference achievable when considering the sub_list, [l[i],...,l[n-1]] with 𝑠1 being the sum of elements already committed to list l1 and 𝑠2

being the sum of elements already committed to l2.

𝗆𝗂𝗇𝖠𝖻𝗌𝖣𝗂𝖿𝖿(𝑖,𝑠1,𝑠2)={???min(𝗆𝗂𝗇𝖠𝖻𝗌𝖣𝗂𝖿𝖿(𝑖+1,???,𝑠2),𝗆𝗂𝗇𝖠𝖻𝗌𝖣𝗂𝖿𝖿(𝑖+1,𝑠1,???))𝑖≥𝑛 ← sub_list is empty𝑖≤𝑛−1 ← assign l[i] to l1 or l2

Implement the function compute_Best_Partition(l) that takes in a list l and returns the partition as a tuple of lists (l1, l2).

Assume that all elements of the list l are positive whole numbers. Complete and memo the recurrence above.