ปัญหาผลรวมย่อย

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

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

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

Input:
This algorithm takes a set of numbers, and a sum value.
The Set: {10, 7, 5, 18, 12, 20, 15}
The sum Value: 35
Output:
All possible subsets of the given set, where sum of each element for every subsets is same as the given sum value.
{10,  7,  18}
{10,  5,  20}
{5,  18,  12}
{20,  15}

อัลกอริทึม

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

ป้อนข้อมูล - ชุดและชุดย่อยที่กำหนด ขนาดของชุดและชุดย่อย ผลรวมของชุดย่อย จำนวนองค์ประกอบในชุดย่อย และผลรวมที่กำหนด

ผลลัพธ์ − ชุดย่อยที่เป็นไปได้ทั้งหมดที่มีผลรวมเท่ากับผลรวมที่กำหนด

Begin
   if total = sum, then
      display the subset
      //go for finding next subset
      subsetSum(set, subset, , subSize-1, total-set[node], node+1, sum)
      return
   else
      for all element i in the set, do
         subset[subSize] := set[i]
         subSetSum(set, subset, n, subSize+1, total+set[i], i+1, sum)
      done
End

ตัวอย่าง

#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);     //print the subset
      subsetSum(set,subSet,n,subSize-1,total-set[nodeCount],nodeCount+1,sum);     //for other subsets
      return;
   }else {
      for( int i = nodeCount; i < n; i++ ) {     //find node along breadth
         subSet[subSize] = set[i];
         subsetSum(set,subSet,n,subSize+1,total+set[i],i+1,sum);     //do for next node in depth
      }
   }
}

void findSubset(int set[], int size, int sum) {
   int *subSet = new int[size];     //create subset array to pass parameter of subsetSum
   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);
}

ผลลัพธ์