Choosing k out of N numbers from 2 arrays with highest total value

Try this. It takes O(N^2) time and it is fairly simple.

def maxPicks(A,B,C,k):
    # returns the tuple (list of entries picked in A, list of entries picked in B, total value)

    # BASE CASE
    if k == 0:
        return ([], [], 0)
    aMax = max(A)
    bMax = max(B)
    cMax = max(C)

    if (aMax + bMax) > cMax:
        aIdx = A.index(aMax)
        bIdx = B.index(bMax)
        B[aIdx] = C[aIdx] - A[aIdx]
        A[aIdx] = -2
        C[aIdx] = -1
        A[bIdx] = C[bIdx] - B[bIdx]
        B[bIdx] = -2
        C[bIdx] = -1
        nextPicks = maxPicks(A,B,C,k-1)
        return (nextPicks[0] + [aIdx], nextPicks[1] + [bIdx], nextPicks[2] + aMax + bMax)
    else:
        cIdx = C.index(cMax)
        A[cIdx] = -1
        B[cIdx] = -1
        C[cIdx] = -1
        nextPicks = maxPicks(A,B,C,k-1)
        return (nextPicks[0] + [cIdx], nextPicks[1] + [cIdx], nextPicks[2] + cMax)

Here's how it works:

The base case should be self explanatory. Otherwise we will compare the sum of the maximum of all entries in A and the maximum of all entries in B to the maximum of all entries in C. If this sum is larger than it is safe to pick these entries from A and B, but before making more picks we will need to set the entries we picked as well as their corresponding entries in C to a negative value. As a side note I do assume that all values in A, B and C are originally nonnegative so by setting them negative we forbid our algorithm from picking them again. If this assumption is wrong you might want to set these values to something extremely negative to prohibit double picks. We also see that if we picked A[i] the value of B[i] is now whatever C[i]-A[i] was, because picking B[i] will lose us the value in A[i] and give us the value in C[i] same for the entry A[j] if we pick B[j].

If on the other hand, the greatest entry in C was greater than or equal to aMax+bMax we want to pick it (by picking the corresponding entries in both A and B, because no other picks of entries in A and B or just C alone would be more valuable. At this point we know we don't want to re-pick A[i],B[i], or C[i] again, so we set them all negative.

This can be solved with dynamic programming.

# Helper function to get out of the data structure.
def get_nested_array (data, path):
    for x in path:
        if data is None or len(data) <= x:
            return None
        else:
            data = data[x]
    return data

# Helper function to set data in the data structure.
def set_nested_array (data, path, value):
    # Navigate there
    for x in path[0:len(path)-1]:
        while len(data) <= x:
            data.append([])
        if data[x] is None:
            data[x] = []
        data = data[x]
    while len(data) <= path[-1]:
        data.append(None)
    data[path[-1]] = value

# Is this option better than what is there?  If so, then add it.
def possibly_add_choice (best_choice, pos, i, j, current_sum, last_i, last_j):
    best_prev = get_nested_array(best_choice, [pos, i, j])
    if best_prev is None or best_prev[0] < current_sum:
        set_nested_array(best_choice, [pos, i, j], (current_sum, last_i, last_j))

# Our program.
def optimal_choices (k, A, B, C):
    # best_choice[pos][i][j] = (max_sum, last_a, last_b)
    # where:
    #    We have made all choices in the range 0..pos-1
    #    We chose i out of A
    #    We chose j out of B
    # and
    #    max_sum is the best possible sum
    #    last_a is the last index chosen from a
    #    last_b is the last index chosen from b
    # then we can find the answer working backwards from
    # best_choice[len(A)][k][k]
    #
    best_choice = []

    # Enter the empty set answer
    set_nested_array(best_choice, [0, 0, 0], (0, None, None))

    for pos in range(len(A)):
        best_choice.append([])
        best_choice_for_pos = best_choice[pos]
        for i in range(k+1):
            if len(best_choice_for_pos) <= i:
                break
            best_choice_for_i = best_choice_for_pos[i]
            for j in range(k+1):
                if len(best_choice_for_i) <= j:
                    break
                last_sum, last_i, last_j = best_choice_for_i[j]

                # Try all 4 things we can choose here.  Nothing, or A or B or both.
                possibly_add_choice(best_choice, pos+1, i, j, last_sum, last_i, last_j)
                possibly_add_choice(best_choice, pos+1, i+1, j, last_sum + A[pos], pos, last_j)
                possibly_add_choice(best_choice, pos+1, i, j+1, last_sum + B[pos], last_i, pos)
                possibly_add_choice(best_choice, pos+1, i+1, j+1, last_sum + C[pos], pos, pos)

    # Now we have the answer, it is just a question of decoding it.
    if get_nested_array(best_choice, [len(A), k, k]) is None:
        return (None, None)
    else:
        choose_a = []
        choose_b = []
        best_spot = [len(A), k, k]
        max_sum, last_i, last_j = get_nested_array(best_choice, best_spot)
        while last_i is not None or last_j is not None:
            # Figure out where we last had a choice and what was chosen.
            if last_i is None:
                last_pos = last_j
                i_dec = 0
                j_dec = 1
            elif last_j is None:
                last_pos = last_i
                i_dec = 1
                j_dec = 0
            else:
                last_pos = max(last_i, last_j)
                i_dec = 0
                j_dec = 0
                if last_pos == last_i:
                    i_dec = 1
                if last_pos == last_j:
                    j_dec = 1

            # record the choice.
            if 1 == i_dec:
                choose_a.append(last_pos)
            if 1 == j_dec:
                choose_b.append(last_pos)

            # Go back to that spot
            max_sum, last_i, last_j = get_nested_array(best_choice, [last_pos, k-len(choose_a), k-len(choose_b)])

        # We walked backwards to generate these lists.  So they are currently reversed.
        return (list(reversed(choose_a)), list(reversed(choose_b)))

print(optimal_choices(2, [3, 1, 1, 0 ], [1, 3, 0, 1], [4, 4, 3, 2]))

If you expand A and B into a list of index pairs with their respective sums (applying exceptions from C), you can iteratively take the maximum sum and exclude the corresponding pairs at each step. This will select the highest possible totals from the remaining pairs at each iteration:

def maxSum(A,B,C,K):
    S = [ ([a+b,C[i]][i==j],i,j) for i,a in enumerate(A)  
                                 for j,b in enumerate(B)]
    usedA,usedB  = set(),set()
    for _ in range(K):
        _,i,j = max(s for s in S if not(s[1] in usedA or s[2] in usedB))
        usedA.add(i)
        usedB.add(j)
    return sorted(usedA),sorted(usedB)

output:

A = [3, 1, 1, 0]   
B = [1, 3, 0, 1]  
C = [4, 4, 3, 2]
print(maxSum(A,B,C,2)) # ([0, 2], [1, 2])   total is 9

A = [1,2,3,4]
B = [4,5,6,2]
C = [5,9,9,6]

print(maxSum(A,B,C,2)) # ([1, 3], [1, 2])  total is 19

print(maxSum(A,B,C,3)) # ([1, 2, 3], [0, 1, 2]) total is 26