ব্যাকট্র্যাকিং হল ডায়নামিক প্রোগ্রামিং সমস্যা সমাধানের একটি কৌশল। এটি ধাপে ধাপে কাজ করে এবং সেই পথগুলিকে প্রত্যাখ্যান করে যা সমাধানের দিকে নিয়ে যায় না এবং ট্র্যাকব্যাক (ফিরে যায়) আগের অবস্থানে চলে যায়৷
উপসেট সমষ্টি সমস্যায়, আমাদের একটি সেটের উপসেটটি এমনভাবে খুঁজে বের করতে হবে যাতে এই উপসেটের উপাদান একটি প্রদত্ত সংখ্যা K পর্যন্ত যোগ করে। সেটের সমস্ত উপাদান ধনাত্মক এবং অনন্য (কোনও অনুলিপি উপাদান নেই )।
এর জন্য, আমরা উপসেট তৈরি করব এবং তাদের যোগফল প্রদত্ত সংখ্যা k এর সমান কিনা তা পরীক্ষা করব। আসুন একটি সমাধান তৈরি করার জন্য একটি প্রোগ্রাম দেখি।
উদাহরণ
#include <stdio.h>
#include <stdlib.h>
static int total_nodes;
void printValues(int A[], int size){
for (int i = 0; i < size; i++) {
printf("%*d", 5, A[i]);
}
printf("\n");
}
void subset_sum(int s[], int t[], int s_size, int t_size, int sum, int ite, int const target_sum){
total_nodes++;
if (target_sum == sum) {
printValues(t, t_size);
subset_sum(s, t, s_size, t_size - 1, sum - s[ite], ite + 1, target_sum);
return;
}
else {
for (int i = ite; i < s_size; i++) {
t[t_size] = s[i];
subset_sum(s, t, s_size, t_size + 1, sum + s[i], i + 1, target_sum);
}
}
}
void generateSubsets(int s[], int size, int target_sum){
int* tuplet_vector = (int*)malloc(size * sizeof(int));
subset_sum(s, tuplet_vector, size, 0, 0, 0, target_sum);
free(tuplet_vector);
}
int main(){
int set[] = { 5, 6, 12 , 54, 2 , 20 , 15 };
int size = sizeof(set) / sizeof(set[0]);
printf("The set is ");
printValues(set , size);
generateSubsets(set, size, 25);
printf("Total Nodes generated %d\n", total_nodes);
return 0;
} আউটপুট
The set is 5 6 12 54 2 20 15 5 6 12 2 5 20 Total Nodes generated 127
