2
$\begingroup$

Given two arrays both of length n, you have to choose exactly k values from the array 1 and n-k values from the other array, such that the sum of these values is maximum, with constraint that if you choose a value from some index of any of the array you cannot choose from same index of second array.

I have encountered this type of question in many places but never able to solve it, and I always have an Intuition that this is a dynamic programming problem but never able to prove it. I do not quite understand If there exist a dynamic solution or not?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ @Evil Edited it, seems its was greedy problem before, now changed? $\endgroup$
    – Pushkar Soni
    Jun 16, 2019 at 0:38
  • $\begingroup$ Do you mean "given two arrays both of length n and a number $k$, you have to choose exactly k values from the array 1 and n-k values from the other array, such that the sum of these values is maximum."? $\endgroup$
    – John L.
    Jun 16, 2019 at 4:03
  • $\begingroup$ @Apass.Jack Yes but our array cannot use two values which came from same index $\endgroup$
    – Pushkar Soni
    Jun 16, 2019 at 5:14
  • $\begingroup$ @Apass.Jack I've found a dp solution which works in O(n*k), thought you would want to know, its 2-D dp ,we need to create dp[n][k], lets define dp[i][j] as the maximum value one can obtain if we choose exactly k values from array1 up until now, for calculation part dp[i][j]=max(arr2[i] + dp[i-1][j], arr2[i]+dp[i-1][j-1]), that is max(current value is part of solution, its not part of solution). should I post it as a solution? not sure if I committed any mistake, I only tried it on two test cases not too big, not sure if my solution is entirely correct. $\endgroup$
    – Pushkar Soni
    Jun 26, 2019 at 1:08
  • $\begingroup$ "lets define dp[i][j] as the maximum value one can obtain if we choose exactly k values", you meant exactly "i values". It is up to you to post the dp approach or not. Although the dp approach is slower in the case of 2 arrays, it can be generalized to 3 or more arrays easily $\endgroup$
    – John L.
    Jun 26, 2019 at 2:40

3 Answers 3

Reset to default
1
$\begingroup$

There are two ways to interpret the problem.

$k$ is part of the input

Let $a=(a_1, a_2, \cdots, a_n)$ and $b=(b_1, b_2, \cdots, b_n)$ be the two given array. Suppose we have chosen $k$ values from array $a$, $a_i$ where $i$ ranges over some index set $I$ that has $k$ elements. Then we have to choose the $n-k$ values from array $b$, $b_j$ where $j$ ranges over all indices that are not in $I$. The sum of all numbers are

$$\sum_{i\in I}a_i+\sum_{i\not\in I}b_i=(\sum_{i\in I}a_i-\sum_{i\in I}b_i) + (\sum_{i\in I}b_i+\sum_{i\not\in I}b_i)=\sum_{i\in I}(a_i-b_i)+\sum_ib_i$$

Since $\sum_ib_i$ is a constant, the sum reaches the maximum if $\sum_{i\in I}(a_i-b_i)$ reaches the maximum. So we can select the $k$ largest elements in the array $a-b=(a_1-b_1, a_2-b_2, \cdots, a_n-b_n)$. The indices of the those elements are the indices of the elements in $a$ that we should choose.

The $k$ largest element can be selected in $O(n)$ time using quickselect, this algorithm can be implemented in $O(n)$ time. It can also be implemented in $O(n\log n)$ easily by sorting the array $a-b.$

$k$ is not part of the input

Solve the previous problem for $k=0$. Let the maximum sum obtained by $m_0$.
Solve the previous problem again but for $k=1$. Let the maximum sum obtained by $m_1$.
And so on.

Find the maximum number among $m_0, m_1, \cdots, m_n$. That is the maximum sum we want in this interpretation the problem. A bit of extra bookkeeping will let us know the numbers we should select to reach that maximum sum.

Exercises

Exercise 1. How about the case of smallest sum?

Exercise 2. How about exactly $k-1$ values from the first array and $n-k$ values from the other array?

Improve this answer
$\endgroup$
4
  • $\begingroup$ I didn't understand RHS of the equation, can you help me with that? I mean why does that work? in the array a-b many values will go negative. $\endgroup$
    – Pushkar Soni
    Jun 16, 2019 at 5:37
  • $\begingroup$ Check this example, $(a_1+a_3)+(b_2+b_4)=((a_1-b_1)+(a_3-b_3))+(b_1+b_2+b_3+b_4)$ $\endgroup$
    – John L.
    Jun 16, 2019 at 5:56
  • $\begingroup$ I got it Thanks, very elegant solution requiring mathematics, So this is Greedy problem Requiring sorting(NLogn), not a Dynammic problem? Am I correct? $\endgroup$
    – Pushkar Soni
    Jun 16, 2019 at 6:07
  • $\begingroup$ You are. The approach is certainly not dynamic programming. The algorithm could be called a greedy algorithm. $\endgroup$
    – John L.
    Jun 16, 2019 at 6:23
1
$\begingroup$

Answering My own Question: though time complexity of the greedy solution is much better.

Dynamic Programming Approach:

We Have: $array1$ and $array2$ both of length $n$ and we are required to choose exactly $k$ values from $array1$ and $n-k$ values from $array2$

Now we iterate through each value pairs from both the array and fill the array-dp row by row as we iterate through each column.

Create 2-Array dp[n][k], Where,

$ n$ - $length$ $of$ $each$ $array$

$ k$ - $no$ $of$ $values$ $to$ $be$ $taken$ $from$ $array1$

Definition: $dp[i][j]$ - is the maximum value one can obtain if we are done iterating through $i$ value pairs and exactly $j$ values are taken from $array1$

Formula: $dp[i][j]$ $=$ $max(array2[i]+dp[i-1][j],array1[i]+dp[i-1][j-1])$

Explanation of Formula: for each $(i,j)$ in the table we choose the maximum between two values that are,

  1. if we choose a value from $array2$ that means we now need to choose exactly $j$ values from previous $i-1$ value pairs.(remember we needed to choose exactly $k$ values from $array1$)
  2. if we choose a value from $array1$ that means we now have to choose exactly $j-1$ values from previous $i-1$ value pairs.

To get the maximum value obtainable we look for value of dp[n][k]

Time complexity: $O(n*k)$

Improve this answer
$\endgroup$
2
  • $\begingroup$ This answer looks good. $\endgroup$
    – John L.
    Jun 26, 2019 at 19:10
  • $\begingroup$ How to initiate dp array $\endgroup$
    – Kitwradr
    Oct 25, 2022 at 2:16
0
$\begingroup$

Given two arrays A and B, for each index i your sum includes either A[i] or B[i]. You can start adding all B[i], then picking k indexes i and replacing B[i] with A[i], increasing the sum by (A[i] - B[i]).

You make the sum largest by calculating all values A[i] - B[i] and storing them into an array C, selecting the k largest values in C, and adding them to the sum.

Finding the k-largest element of an array can be done in O(n), and adding the k largest elements can again be done in linear time (add all elements that are greater than the k-largest element and count them at the same time. If you found k' elements greater than the k-largest, then there are at least k-k' elements equal to the k-largest.

Pseudocode: Let S be the sum of B[i] for 1 ≤ b ≤ n. Let C[i] = A[i] - B[i] for 1 ≤ i ≤ n. Find the k largest element of C, and let its value be K. Add all elements C[i] to S where 1 ≤ i ≤ n and C[i] > k. Let k' be the number of elements C[i] for 1 ≤ i ≤ n with C[i] > k. Increase S by (k - k') * K.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.