サブセット和のためのC/C ++プログラム（バックトラッキング）

バックトラッキングは、動的計画法の問題を解決するための手法です。それは段階的に進むことによって機能し、解決策につながらないパスを拒否し、前の位置にトラックバック（戻る）します。

サブセット和問題では、セットのサブセットが、このサブセットの要素が指定された数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