เซตย่อยขนาดสูงสุดที่มีผลรวมเท่ากับค่าที่กำหนดใน C++

ข้อความปัญหา

ได้รับอาร์เรย์ N องค์ประกอบและค่าเป้าหมาย (sum) ต้องการหาขนาดของเซตย่อย (Subset) ที่ใหญ่ที่สุดซึ่งผลรวมเท่ากับค่าที่กำหนด

ตัวอย่าง

ถ้าอาร์เรย์อินพุตคือ arr = { 2, 3, 5, 10 } และ sum = 20 ผลลัพธ์จะเป็น 4 เพราะ

2 + 3 + 5 + 10 = 20 ซึ่งเท่ากับผลรวมที่กำหนด

อัลกอริทึม

เราสามารถใช้การเขียนโปรแกรมแบบไดนามิก (Dynamic Programming) เพื่อแก้ปัญหานี้

เพื่อนับเซตย่อยสูงสุด เราใช้อาร์เรย์ DP อีกตัวหนึ่ง (เรียกว่า "count array") โดยที่ count[i][j] คือค่าสูงสุดของ:

• count[i][j-1] - ไม่นำองค์ประกอบปัจจุบันเข้าไป
• count[i - X][j-1] + 1 - นำองค์ประกอบปัจจุบันเข้าไป (X คือค่าขององค์ประกอบที่เลือก)

ตัวอย่างโค้ด

#include<bits/stdc++.h>
using namespace std;

int isSubsetSum(int set[], int n, int sum) {
    bool subset[sum + 1][n + 1];
    int count[sum + 1][n + 1];
    
    for (int i = 0; i <= n; i++) {
        subset[0][i] = true;
        count[0][i] = 0;
    }
    for (int i = 1; i <= sum; i++) {
        subset[i][0] = false;
        count[i][0] = -1;
    }
    for (int i = 1; i <= sum; i++) {
        for (int j = 1; j <= n; j++) {
            subset[i][j] = subset[i][j - 1];
            count[i][j] = count[i][j - 1];
            if (i >= set[j - 1]) {
                subset[i][j] = subset[i][j] || subset[i - set[j - 1]][j - 1];
                if (subset[i][j]) {
                    count[i][j] = max(count[i][j - 1], count[i - set[j - 1]][j - 1] + 1);
                }
            }
        }
    }
    return count[sum][n];
}

int main() {
    int set[] = { 2, 3, 5, 10 };
    int sum = 20;
    int n = 4;
    cout << "Result = " << isSubsetSum(set, n, sum) << endl;
}

ผลลัพธ์

Result = 4

คำอธิบาย

ตาราง DP subset[i][j] บอกว่าสามารถสร้างผลรวม i ได้จาก j องค์ประกอบแรกหรือไม่ ส่วน count[i][j] เก็บจำนวนองค์ประกอบสูงสุดที่ทำให้ได้ผลรวม i

ความซับซ้อนเวลา: O(sum × n), ความซับซ้อนพื้นที่: O(sum × n)