Last Updated: 18 Jan, 2022

Closest Cost

Moderate

Asked in company

Problem statement

Ninja is given the task to create a perfect gift for the king. He has ‘N’ wraps to choose from which he can choose to wrap the gifts. He also has ‘M’ gifts from which he can choose the gifts for the king. To choose the gifts, he sets some rules:

1) He must select exactly one wrapper to wrap all the chosen gifts.
2) He can select one or more gifts or no gifts at all.
3) He has 2 copies of the same gift. So, he can take 0 or 1 or 2 copies of each gift.

He also has a number ‘X’. He decided to spend in such a way that the total cost is as close as ‘X’. If there are multiple answers, print the minimum one.

For example:

Let’s say you have two wrappers with cost [1, 2] and three gifts with cost [3, 4, 5] and ‘X’ = 7. In the first case, you select wrapper number ‘2’ and gift number ‘1’ and ‘3’, so your total cost will be 2 + 3 + 5 = 10. While in the second case, you select wrapper number ‘1’ and gift number ‘2’, so your total cost will be 1 + 4 = 5. So out of both the cases, second case is closer to ‘X’ as abs(7 - 5) = 2 and abs(7 - 10) = 3.

Input Format-

First-line contains ‘T’, denoting the number of Test cases.
For each Test case:
The first line contains three space-separated integers, ‘N’, ‘M’ and ‘X’, denoting the number of the Wrappers, Gifts and closest number till you have to get the total cost, respectively.
The following line contains an array ‘W’ of ‘N’ space-separated integers, denoting the cost of the ‘ith’ wrapper.
The following line contains an array ‘G’ of ‘M’ space-separated integers, denoting the cost of the ‘ith’ gift.

Output Format-

For each test case, print an integer denoting the total cost that is as close as ‘X’.

Constraints -

1 <= ‘T’ <= 10
1 <= ‘N’ <= 10
1 <= ‘M’ <= 10
1 <= W[i], G[i] <= 10^4
1 <= ‘X’ <= 10^9

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Approach: Let's say we have selected the ‘ith’ wrapper. Then we iterate in the gifts and try to select some gifts. There will be three ways to choose each gift. First, select one piece of that gift. Second, select two pieces of that gift, and lastly, do not select any piece of that gift. We can easily implement this with recursion since we have only three choices when selecting a particular gift. We will now take a particular wrapper and start choosing gifts following the above ways.

Algorithm:

Func recursion(i, cost, bestCost):
If (cost >= T) or ( i >= M).
If abs(X - cost) < abs(X - bestCost).
bestCost = cost.
Else if abs(X - cost) = abs(X - bestCost).
bestCost = min(bestCost, cost).
Else.
Add zero gift piece, call the function ‘recursion’ while updating the cost.
Add one gift piece, call the function ‘recursion’ while updating the cost.
Add two gift pieces, call the function ‘recursion’ while updating the cost.
Func Main().
Create a variable ‘ans’ and initialize it to ‘INT_MAX’.
For each wrapper.
Call the function ‘recursion’.
Print ‘ans’.

Solve now