เจอกันกลางชวา

เราได้รับอาร์เรย์และค่าผลรวม คำสั่งปัญหาคือการคำนวณผลรวมของเซตย่อยสูงสุดซึ่งไม่เกินค่ารวมที่กำหนด เราไม่สามารถใช้วิธีเดรัจฉานที่นี่ได้เนื่องจากโครงสร้างของอาร์เรย์ที่ให้มานั้นไม่เหมือนกับวิธีการหารและพิชิต

ให้เราดูสถานการณ์อินพุตเอาต์พุตต่างๆ สำหรับสิ่งนี้ -

ให้เราเข้าใจด้วยตัวอย่าง

ป้อนข้อมูล − arr ยาว[] ={ 21, 1, 2, 45, 9, 8 } ที่ได้รับ_Sum =12

ผลผลิต −ชุดย่อยผลรวมสูงสุดที่มีผลรวมน้อยกว่าหรือเท่ากับผลรวมที่ให้มา-->12

คำอธิบาย −อาร์เรย์ถูกแบ่งออกเป็นชุดย่อย 2 ชุด อันแรกมีองค์ประกอบ n/2 และอันหลังมีองค์ประกอบที่เหลือ ผลรวมย่อยที่เป็นไปได้ทั้งหมดของชุดย่อยแรกจะถูกคำนวณและเก็บไว้ในอาร์เรย์ A และในทำนองเดียวกันผลรวมของชุดย่อยของชุดย่อยต่อมาจะถูกคำนวณและจัดเก็บไว้ในอาร์เรย์ B ในที่สุดปัญหาย่อย 2 ปัญหาจะถูกรวมเข้าด้วยกันเพื่อให้ผลรวมของพวกมันน้อยกว่าหรือเท่ากับ เพื่อผลรวม

ป้อนข้อมูล − arr ยาว[] ={ 2, 12, 16, 25, 17, 27 } ที่ได้รับ_Sum =24;

ผลผลิต −ผลรวมย่อยสูงสุดที่มีผลรวมน้อยกว่าหรือเท่ากับผลรวมที่ให้มา-->19

คำอธิบาย −อาร์เรย์ถูกแบ่งออกเป็นชุดย่อย 2 ชุด อันแรกมีองค์ประกอบ n/2 และอันหลังมีองค์ประกอบที่เหลือ ผลรวมย่อยที่เป็นไปได้ทั้งหมดของชุดย่อยแรกจะถูกคำนวณและเก็บไว้ในอาร์เรย์ A และในทำนองเดียวกันผลรวมของชุดย่อยของชุดย่อยต่อมาจะถูกคำนวณและจัดเก็บไว้ในอาร์เรย์ B ในที่สุดปัญหาย่อย 2 ปัญหาจะถูกรวมเข้าด้วยกันเพื่อให้ผลรวมของพวกมันน้อยกว่าหรือเท่ากับ เพื่อผลรวม

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้ −

• สร้างอาร์เรย์ประเภทข้อมูลแบบยาวและตัวแปรประเภทข้อมูลแบบยาวและตั้งค่าเป็น 10 เรียกใช้ฟังก์ชันเป็น

• ภายในเมธอด คำนวณSubsetSum(arr, arr.length, given_Sum))

  • เรียกเมธอดเป็น dissolve_subarray(a, A, len / 2, 0) และ Solv_subarray(a, B, len - len / 2, len / 2)

  • คำนวณขนาดของ A และ B แล้วจัดเรียงอาร์เรย์ B โดยใช้เมธอด sort()

  • เริ่มวนรอบ FOR จาก i ถึง 0 จนถึง i น้อยกว่าขนาดของอาร์เรย์ A ตรวจสอบว่า A[i] น้อยกว่าเท่ากับ given_Sum แล้วตั้งค่า get_lower_bound tocalculate_lower_bound(B, given_Sum - A[i]) ตรวจสอบ IF get_lower_boundto size_B OR B[get_lower_bound] ไม่เท่ากับ (given_Sum - A[i])) ให้ลดค่า get_lower_bound ทีละ 1

  • ตรวจสอบว่า B[get_lower_bound] + A[i]) มากกว่า max แล้วตั้งค่า max เป็นB[get_lower_bound] + A[i]

  • ผลตอบแทนสูงสุด

• ภายในเมธอด Solv_subararay(long a[], long x[], int n, int c)

  • เริ่มวนซ้ำ FOR จาก i ถึง 0 จนถึง i น้อยกว่า (1 <

  • เริ่มวนซ้ำ FOR จาก j ถึง 0 ถึง j น้อยกว่า n ภายในลูป ให้ตรวจสอบว่า i &(1 <

  • ตั้งค่า x[i] เพื่อผลรวม

• ภายในเมธอด คำนวณ _lower_bound(long a[], long x)

  • ประกาศตัวแปรเป็นซ้ายถึง -1 และขวาไปยาวความยาวของอาร์เรย์ 1

  • เริ่มวนซ้ำในขณะที่ซ้าย + 1 น้อยกว่าขวา ภายใน while ให้ตั้งค่า m เป็น (ซ้าย + ขวา)>>> 1. ตรวจสอบว่า a[m] มากกว่า x แล้วตั้งค่าขวาเป็น 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