ปัญหาผลรวมย่อย (Subset Sum Problem)

บทนำ

กำหนดชุดจำนวนเต็มและค่าเป้าหมาย (Target Sum) ต้องการหา Subset ของชุดที่กำหนด ซึ่งผลรวมของสมาชิกเท่ากับค่าเป้าหมาย

ใช้ Backtracking: ลองเลือกสมาชิกเข้าสู่ Subset หากไม่ถูกต้องให้ Backtrack กลับไปลองสมาชิกอื่น

อินพุตและเอาต์พุต

Input: Set: {10, 7, 5, 18, 12, 20, 15}, Sum Value: 35
Output: ทุก Subset ที่ผลรวมเท่ากับ 35:
        {10, 7, 18}
        {10, 5, 20}
        {5, 18, 12}
        {20, 15}

อัลกอริทึม

subsetSum(set, subset, n, subSize, total, node, sum)

Input: เซต, เซตย่อย, ขนาดเซตและเซตย่อย, ผลรวมปัจจุบัน, จำนวนสมาชิก, ผลรวมเป้าหมาย
Output: ทุก Subyte ที่ผลรวมเท่ากับเป้าหมาย

Begin
    if total = sum then
        แสดง subset
        subsetSum(set, subset, n, subSize-1, total-set[node], node+1, sum)  // หา subset ถัดไป
        return
    else
        for i ทุกสมาชิกในเซต do
            subset[subSize] := set[i]
            subSetSum(set, subset, n, subSize+1, total+set[i], i+1, sum)
        done
End

ตัวอย่างโค้ด (C++)

#include <iostream>
using namespace std;

void displaySubset(int subSet[], int size) {
    for(int i = 0; i < size; i++) cout << subSet[i] << "  ";
    cout << endl;
}

void subsetSum(int set[], int subSet[], int n, int subSize, int total, int nodeCount, int sum) {
    if(total == sum) {
        displaySubset(subSet, subSize);
        subsetSum(set, subSet, n, subSize-1, total-set[nodeCount], nodeCount+1, sum);
        return;
    } else {
        for(int i = nodeCount; i < n; i++) {
            subSet[subSize] = set[i];
            subsetSum(set, subSet, n, subSize+1, total+set[i], i+1, sum);
        }
    }
}

void findSubset(int set[], int size, int sum) {
    int *subSet = new int[size];
    subsetSum(set, subSet, size, 0, 0, 0, sum);
    delete[] subSet;
}

int main() {
    int weights[] = {10, 7, 5, 18, 12, 20, 15};
    int size = 7;
    findSubset(weights, size, 35);
}

ผลลัพธ์