ในปัญหานี้ เราต้องสร้างโค้ด C++ เพื่อตรวจสอบว่าอาร์เรย์สามารถแบ่งเป็นสองเซตย่อยที่มีผลรวมเท่ากันได้หรือไม่ นอกจากนี้ยังต้องตรวจสอบเงื่อนไขว่าผลรวมขององค์ประกอบในทั้งสองเซตย่อยเท่ากันจริงหรือไม่ ปัญหาการแบ่งพาร์ติชันเป็นรูปแบบหนึ่งของปัญหา Subset Sum Problem ซึ่งเป็นรูปแบบหนึ่งของ Knapsack Problem เราจะใช้ภาษา C++ ในการแก้ปัญหานี้ ต้องคืนค่าสตริง "Yes" หรือ "No" ขึ้นอยู่กับว่าเงื่อนไขเป็นจริงหรือไม่
ข้อมูลนำเข้า
arr[] = {6, 4, 8, 12, 15}
ข้อมูลส่งออก
Is possible to divide into two subsets of equal sum
แนวทางการแก้ปัญหา
เป้าหมายคือหาผลรวมของทุกองค์ประกอบในเซต เมื่อผลรวมของอาร์เรย์เป็นคี่ เราไม่สามารถแบ่งเป็นสองเซตได้ ระบุเซตย่อยที่มีผลรวม sum/2 เมื่อผลรวมเป็นคู่ ใช้งานอาร์เรย์ที่กำหนด ตรวจสอบองค์ประกอบแต่ละตัวทีละตัว แล้วเลือกหนึ่งในสองทางเลือก:
- รวมองค์ประกอบปัจจุบันในเซตย่อย แล้วเพิ่มส่วนที่เหลือเพื่อให้ได้ผลรวม
- นำองค์ประกอบปัจจุบันออกจากเซตย่อย แล้วทำซ้ำกับองค์ประกอบอื่นๆ
สุดท้าย คืนค่า true ถ้าองค์ประกอบปัจจุบันถูกรวมหรือไม่อยู่ในเซตย่อย มิฉะนั้นคืนค่า false การเรียกซ้ำจะสิ้นสุดเมื่อไม่มีองค์ประกอบเหลือ หรือผลรวมติดลบ ในกรณีที่ผลรวมเป็น 0 เราคืนค่า true หมายถึงพบเซตย่อยแล้ว
ตัวอย่างโค้ด (วิธีเรียกซ้ำ)
#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: Dynamic Programming
เมื่อผลรวมขององค์ประกอบไม่มากเกินไป ปัญหานี้สามารถแก้ได้ด้วย Dynamic Programming สร้างอาร์เรย์ 2D part[][] ขนาด (sum/2 + 1)*(n+1) สร้างคำตอบแบบ bottom-up โดยแต่ละค่าที่เติมมีคุณสมบัติดังนี้ เราสามารถแก้ปัญหานี้ด้วยอาร์เรย์ 2D ขนาด (sum/2 + 1)*(n + 1) แทนที่จะเป็นขนาด (sum/2 + 1)*(n + 1)
ตัวอย่างโค้ด (Dynamic Programming)
#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++ โค้ดนี้สามารถเขียนใน Java, Python และภาษาอื่นๆ ได้ เราแก้ปัญหาการแบ่งพาร์ติชันโดยใช้การเรียกซ้ำและอาร์เรย์ในภาษา C++ เป็นโค้ดพื้นฐานแต่มีประโยชน์มากในการแก้ปัญหาต่างๆ
