The thief problem in Java

 Problem Statement:

Given an array of N items and a value K, the task is to find K items that have the maximum combined value. In other words, we need to select K items from the given array such that the sum of their values is maximum.

Examples: To understand the problem better, let's consider two examples:

• Input: arr[] = {3, 7, 2, 5, 12, 30}, K = 3 Output: 49 Items picked are: 7, 12, 30

  In this example, the given array has 6 items, and we need to select 3 items that have the maximum combined value. The three items with maximum value are 7, 12, and 30. Therefore, the sum of their values is 49.

• Input: arr[] = {8, 10, 2, 50, 80, 20}, K = 4 Output: 160 Picked items are: 10, 50, 80, 20

  In this example, the given array has 6 items, and we need to select 4 items that have the maximum combined value. The four items with maximum value are 10, 50, 80, and 20. Therefore, the sum of their values is 160.

Naive Solution: A simple solution to solve this problem is to find the K largest items in the array and return the sum of their values. This approach can be implemented by sorting the array in decreasing order and selecting the first K items. This method takes O(NK) time. In the worst-case scenario, where K is close to N, the time complexity can reach O(NN).

Better Solution: A better approach to solve this problem is to first sort the array in decreasing order and then select the first K items from the sorted array. Sorting the array takes O(NlogN) time. The overall time complexity of this approach is O(NlogN), which is much faster than the naive solution.

Here is the Java implementation of the better solution:

// Java implementation of the above approach import java.util.*;

class GfG {

java
static int getMaxVal(Integer arr[], int K)
{
   Arrays.sort(arr, Collections.reverseOrder());
   
   int res = 0;
   
   for(int i=0; i<K; i++)
   {
       res += arr[i];
   }
   
   return res;
}

public static void main(String args[])
{
    Integer arr[] = {3, 7, 2, 5, 12, 30};
    int K = 3;
    
    System.out.println(getMaxVal(arr, K));
}

}

The output of the above code for the first example will be:

Output: 49

In conclusion, the problem requires selecting K items with the maximum value from the given array. The naive solution selects K largest items by sorting the array in decreasing order, while the better solution first sorts the array and then selects the first K items from the sorted array. The better solution has a much lower time complexity of O(NlogN) compared to O(NK) for the naive solution, making it a more efficient and faster approach.