ปัญหาพาร์ติชั่นใน C++

ในปัญหานี้ เราต้องสร้างโค้ด C++ เพื่อกำหนดว่าอาร์เรย์สามารถแบ่งออกเป็นสองอาร์เรย์ย่อยที่เท่ากันหรือไม่ นอกจากนี้ เราต้องตรวจสอบเงื่อนไขด้วยว่าผลรวมขององค์ประกอบทั้งหมดในอาร์เรย์ย่อยทั้งสองเหมือนกันหรือไม่ ปัญหาการแบ่งพาร์ติชั่นเป็นตัวแปรของ Subset Sum Problem ซึ่งในทางกลับกัน ปัญหาของเป้ เราจะใช้ภาษาการเขียนโปรแกรม C++ เพื่อจัดการกับปัญหาพาร์ติชั่น เราต้องส่งคืนสตริงที่มีใช่หรือไม่ใช่ขึ้นอยู่กับว่าเงื่อนไขที่ระบุเป็นจริงหรือไม่

ป้อนข้อมูล

arr[] = {6, 4, 8, 12, 15}

ผลผลิต

Is possible to divide into two subsets of equal sum

แนวทางการแก้ปัญหา

เป้าหมายคือการหาผลรวมขององค์ประกอบทั้งหมดในชุด เมื่อผลรวมอาร์เรย์เป็นเลขคี่ เราไม่สามารถแบ่งออกเป็นสองชุดได้ ระบุเซตย่อยด้วย sum/2 เมื่อผลรวมเป็นคู่ ใช้อาร์เรย์ที่กำหนด ตรวจสอบแต่ละองค์ประกอบทีละรายการ แล้วเลือกตัวเลือกใดตัวเลือกหนึ่งต่อไปนี้:

• รวมรายการปัจจุบันในชุดย่อยต่อไป จากนั้นเพิ่มส่วนที่เหลือเพื่อให้ได้ยอดรวม

• เมื่อรายการปัจจุบันถูกลบออกจากชุดย่อยแล้ว ให้ทำซ้ำขั้นตอนสำหรับรายการอื่นๆ

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

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
bool isSubsetSum(int arr[], int n, int sum) {
   if (sum == 0)
      return true;
   if (n == 0 && sum != 0)
      return false;
   if (arr[n - 1] > sum)
      return isSubsetSum(arr, n - 1, sum);
   return isSubsetSum(arr, n - 1, sum) ||
   isSubsetSum(arr, n - 1, sum - arr[n - 1]);
}
bool findPartiion(int arr[], int n) {
   int sum = 0;
   for (int i = 0; i < n; i++)
      sum += arr[i];
   if (sum % 2 != 0)
      return false;
   return isSubsetSum(arr, n, sum / 2);
}
int main() {
   int arr[] = {
      6,
      4,
      8,
      12,
      15
   };
   int n = sizeof(arr) / sizeof(arr[0]);
   if (findPartiion(arr, n) == true)
      cout << "Is possible to divide into two subsets " "of equal sum";
   else
      cout << "Is impossible to divide into two subsets" " of equal sum";
   return 0;
}

ผลลัพธ์

Is impossible to divide into two subsets of equal sum

แนวทางที่ 2

เมื่อส่วนประกอบทั้งหมดไม่ใหญ่เกินไป ปัญหาสามารถจัดการได้โดยใช้โปรแกรมแบบไดนามิก สามารถสร้างส่วนอาร์เรย์ 2 มิติ[][]ขนาด (ผลรวม/2 + 1)*(n+1) ได้ เราอาจสร้างวิธีแก้ปัญหาจากล่างขึ้นบน เพื่อให้แต่ละรายการที่กรอกมีคุณสมบัติดังต่อไปนี้ เราสามารถแก้ปัญหานี้ได้โดยใช้อาร์เรย์ขนาด 2 มิติ (ผลรวม/2 + 1)*(n + 1) แทน ขนาดอาร์เรย์ 2 มิติ (ผลรวม/2 + 1)*(n + 1).

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
bool findPartiion(int arr[], int n) {
   int sum = 0;
   int i, j;
   for (i = 0; i < n; i++)
      sum += arr[i];
   if (sum % 2 != 0)
      return false;
   bool part[sum / 2 + 1];
   for (i = 0; i <= sum / 2; i++) {
      part[i] = 0;
   }
   for (i = 0; i < n; i++) {
      for (j = sum / 2; j >= arr[i]; j--){
         if (part[j - arr[i]] == 1 || j == arr[i])
            part[j] = 1;
      }
   }
   return part[sum / 2];
}
int main() {
   int arr[] = {
      6,
      4,
      8,
      12,
      15
   };
   int n = sizeof(arr) / sizeof(arr[0]);
   if (findPartiion(arr, n) == true)
      cout << "Is possible to divide into two subsets of equal " "sum";
   else
      cout << "Is impossible to divide into two subsets" " of equal sum";
   return 0;
}

ผลลัพธ์

Is impossible to divide into two subsets of equal sum

บทสรุป

ในปัญหานี้ เราได้เรียนรู้วิธีแก้ปัญหาพาร์ติชั่นพร้อมกับโค้ด c++ รหัสนี้ยังสามารถเขียนในภาษาจาวา ไพธอน และภาษาอื่นๆ ได้อีกด้วย เราได้แก้ไขปัญหาพาร์ติชั่นโดยใช้อาร์เรย์แบบเรียกซ้ำในภาษาการเขียนโปรแกรม C++ เป็นรหัสพื้นฐานแต่มีประโยชน์มากมายในการแก้ปัญหา