자바에서 중간에 만나다

<시간/>

배열과 합계 값이 제공됩니다. 문제는 주어진 합계 값을 초과하지 않는 최대 부분 집합 합계를 계산하는 것입니다. 주어진 배열의 구조가 분할 정복 방식과 동일하지 않기 때문에 여기에 무차별 대입 방식을 적용할 수 없습니다.

이에 대한 다양한 입력 출력 시나리오를 살펴보겠습니다. -

예를 들어 이해하자

입력 − long arr[] ={ 21, 1, 2, 45, 9, 8 } long given_Sum =12

출력 - 주어진 합보다 작거나 같은 합을 갖는 최대 합 부분집합-->12

설명 − 배열은 2개의 부분 집합으로 분할됩니다. 첫 번째 요소에는 n/2개의 요소가 있고 나중에는 나머지 요소가 있습니다. 첫 번째 부분 집합의 모든 가능한 부분 집합 합이 계산되어 배열 A에 저장되고 유사하게 나중 부분 집합의 부분 집합 합이 계산되어 배열 B에 저장됩니다. 마지막으로 두 하위 문제는 합이 더 작거나 같도록 병합됩니다. 주어진 합계에.

입력 − long arr[] ={ 2, 12, 16, 25, 17, 27 } long given_Sum =24;

출력 - 주어진 합보다 작거나 같은 합을 갖는 최대 합 부분집합-->19

아래 프로그램에서 사용된 접근 방식은 다음과 같습니다 -

데이터 유형이 긴 배열과 데이터 유형이 긴 변수를 생성하고 10으로 설정합니다. 함수를 countSubsetSum(arr, arr.length, given_Sum))으로 호출합니다.
메소드 내부에서,calculateSubsetSum(arr, arr.length, given_Sum))
- 이 메서드를 solve_subarray(a, A, len / 2, 0) 및 solve_subarray(a, B, len - len / 2, len / 2)
  로 호출합니다.
- A와 B의 크기를 계산한 다음 sort() 메서드를 사용하여 배열 B를 정렬합니다.
- i에서 0까지 FOR 루프를 시작하여 배열 A의 크기보다 작습니다. IF A[i]가 given_Sum보다 작은지 확인한 다음 get_lower_bound를calculate_lower_bound(B, given_Sum - A[i])로 설정합니다. 확인, get_lower_boundto size_B 또는 B[get_lower_bound]가 (given_Sum - A[i]))와 같지 않은 경우 get_lower_bound를 1만큼 감소시킵니다.
- IF B[get_lower_bound] + A[i])가 max보다 큰지 확인한 다음 max를 B[get_lower_bound] + A[i]로 설정합니다.
- 최대 반환
메서드 내부에서 solve_subarray(long a[], long x[], int n, int c)
- i가 (1 <
- j가 n보다 작을 때까지 루프 FOR를 j에서 0으로 시작합니다. 루프 내에서 IF i &(1 <
- x[i]를 합계로 설정
메소드 내부에서, compute_lower_bound(long a[], long x)
- 배열 1의 왼쪽은 -1, 오른쪽은 길이로 변수를 선언합니다.
- 루프 시작 WHILE 왼쪽 + 오른쪽보다 1 작습니다. while 내부에서 m을 (left + right)>>> 1로 설정합니다. IF a[m]이 x보다 큰지 확인하고 right를 m으로 설정합니다.
- 그렇지 않으면 왼쪽을 m으로 설정합니다.
- 오른쪽으로 돌아가세요.

예시

import java.util.*;
import java.lang.*;
import java.io.*;
public class testClass{
   static long A[] = new long[2000005];
   static long B[] = new long[2000005];
   static void solve_subarray(long a[], long x[], int n, int c){
      for (int i = 0; i < (1 << n); i++){
         long sum = 0;
         for (int j = 0; j < n; j++){
            if ((i & (1 << j)) == 0){
               sum += a[j + c];
            }
         }
         x[i] = sum;
      }
   }
   static long calculateSubsetSum(long a[], int len, long given_Sum){
      solve_subarray(a, A, len / 2, 0);
      solve_subarray(a, B, len - len / 2, len / 2);
      int size_A = 1 << (len / 2);
      int size_B = 1 << (len - len / 2);
      Arrays.sort(B);
      long max = 0;
      for (int i = 0; i < size_A; i++){
         if (A[i] <= given_Sum){
            int get_lower_bound = calculate_lower_bound(B, given_Sum - A[i]);
            if (get_lower_bound == size_B || B[get_lower_bound] != (given_Sum - A[i])){
               get_lower_bound--;
            }
            if((B[get_lower_bound] + A[i]) > max){
               max = B[get_lower_bound] + A[i];
            }
         }
      }
      return max;
   }
   static int calculate_lower_bound(long a[], long x){
      int left = -1, right = a.length;
      while (left + 1 < right){
         int m = (left + right) >>> 1;
         if (a[m] >= x){
            right = m;
         }
         else{
            left = m;
         }
      }
      return right;
   }
   public static void main(String[] args){
      long arr[] = { 21, 1, 2, 45, 9, 8 };
      long given_Sum = 12;
      System.out.println("The maximum sum subset having sum less than or equal to the given sum-->" + calculateSubsetSum(arr, arr.length, given_Sum));
   }
}

출력

위의 코드를 실행하면 다음과 같은 출력이 생성됩니다.

The maximum sum subset having sum less than or equal to the given sum-->12