Two new shops are opening inside a new building and k kinds of items are needed to stock shelves at each store. Given the prices of n items in two shops, choose exactly k indices in such a way that the minimum sum of arrays firstShop and secondShop over these indices is maximum.
Specifically, choose exactly k indices (i[1], i[2],...., i[k]) such that the value min(a[i[1]]+a[i[2]]+.... + a[i[k]], b1+b[i[2]]+...+b[i[k]]) is maximized. Find this maximum value.
Example:-
n=5, k=3
firstShop=[6, 3, 6, 5, 1]
secondShop = [1, 4, 5, 9, 2]
Choose the subset of indices as (0, 2, 3).
The value is min(6+6+5, 1+5+9)= 15, which is the maximum possible. Return 15 as the answer
1<=N,array-values<=50
My DP Solution :- O(N*K*|sum1|*|sum2|) ; where sum1 = total sum of first array ; sum2 = total sum of second array but it TLE's how to optimize?
dp[i][k][sum1][sum2] = returns true if it is possible to select k indices from (0....i) such that array1 has sum1 and array2 has sum2.
Instead of keeping track of sum1 and sum2 separately only keep track of the difference, since this is enough to determine the proper strategy.
For example, define dp[n'][k'][diff] as the best possible result if you choose k' indices from the first n', and currently sum1 = diff, sum2 = 0.
Then the recurrence is:
The first term is if you don't choose index n', the second is if you choose it.
Pls teach how to notice such recursive methods. I've learned to picture as a tree, but that never works for me.
Why are you adding min(a[i], b[i]) in diff ?
Sorry, it is a mistake. The i should be n' and that should just be b[i]. I was editing my expression and didn't pay close attention.
The reason is: If you choose index n', then you have to choose k'-1 indices from the first n'-1, and currently sum1 = a[n'] and sum2 = b[n'].
But only the difference in sum1 and sum2 matter, so the best possible result is b[n'] plus the result if you start with sum1 = a[n']-b[n'] and sum2 = 0.
Can you elaborate how dp[n][k][diff] helps in finding final answer ; sum1,sum2 actually tells us they are possible and we take their min for all possible sum1,sum2 and finally print max of all of them how is it possible in dp[n][k][diff]?
The final answer should be dp[n][k][0], because you need to choose k indices from the first n, and you start with sum1 = 0, sum2 = 0.
dp[n][k][0] means best answer such that sum1 = sum2 that is not the requirement of the problem. sum1 and sum2 can be different
Am I getting something wrong please clarify and thanks for your precious time!
No, dp[n'][k'][diff] means best answer such that you start with sum1 = diff, sum2 = 0, and then try to maximize min(sum1, sum2) by choosing k' indices from the first n'.
So in the example you gave, dp[2][1][-3] = 1. Why? Because if we start with sum1 = -3, sum2 = 0, and can choose 1 of the first 2 indices, the best thing to do is to choose the first index. Then sum1 = 3, sum2= 1, and our result will be 1.
Similarly, dp[2][1][7] = 4. If we start with sum1 = 7, sum2 = 0, the best is to choose the second index, which gives a result of 4.
In that case how can one implement it?
diff goes from -u to 0 and then 0 to u
where u = 2500 according to constraints.
That's up to you-- you can use a map, use indices from 0 to 5000, use python with negative indices, overload [] operator, have two different arrays depending on which is bigger, etc.
$$$dp[i][k][sum1] =$$$ maximum possible $$$sum2$$$
You are god!
You should be more careful with your words.
getting wrong answer please anyone correct
which platform you are verifying your sol ?
Just testcase
This gives a complexity of
O(n * k * totalSum)instead of keeping both sums separately.Am I missing something, or is there a hidden flaw in this approach?
~~~~~~~~~~
int n, k; vector first, second; int memo[51][51][2501]; const int INF = 1e9;
/* * STATE: * solve(idx, count, target_a) * - idx: Current item index (0 to n-1) * - count: Remaining items needed to pick (0 to k) * - target_a: Remaining firstShop sum required * * RETURNS: Maximum secondShop sum for this exact configuration */ int solve(int idx, int count, int target_a) { // Base Case 1: Picked required 'k' items if (count == 0) { return (target_a == 0) ? 0 : -INF; } // Base Case 2: Out of items or target_a became negative if (idx == n || target_a < 0) { return -INF; } // Return memoized result if already calculated if (memo[idx][count][target_a] != -1) { return memo[idx][count][target_a]; } // Option 1: Skip current item int skip = solve(idx + 1, count, target_a); // Option 2: Pick current item int pick = -INF; if (target_a >= first[idx]) { int sub_res = solve(idx + 1, count - 1, target_a - first[idx]); if (sub_res != -INF) { pick = second[idx] + sub_res; } } return memo[idx][count][target_a] = max(skip, pick); } int maxMinSum(int n_val, int k_val, vector<int>& firstShop, vector<int>& secondShop) { n = n_val; k = k_val; first = firstShop; second = secondShop; int max_a_sum = 0; for (int x : first) max_a_sum += x; // Reset memoization table with -1 memset(memo, -1, sizeof(memo)); int ans = 0; // Try all possible total sums for firstShop for (int sa = 0; sa <= max_a_sum; ++sa) { int sb = solve(0, k, sa); if (sb >= 0) { ans = max(ans, min(sa, sb)); } } return ans; }~~~~~~