Backtracking là kỹ thuật giải bài toán quy hoạch động. Duyệt từng bước, loại bỏ đường không dẫn đến giải pháp, quay lui (backtrack) về vị trí trước.
Bài toán Subset Sum: tìm tập con của một tập sao cho tổng các phần tử bằng K cho trước. Tất cả phần tử đều dương và duy nhất.
Tạo các tập con, kiểm tra tổng bằng K.
Ví dụ mã nguồn
#include <stdio.h>
#include <stdlib.h>
static int total_nodes;
void printValues(int A[], int size) {
for (int i = 0; i < size; i++)
printf("%5d", A[i]);
printf("\n");
}
void subset_sum(int s[], int t[], int s_size, int t_size, int sum, int ite, int 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("Tap la: ");
printValues(set, size);
generateSubsets(set, size, 25);
printf("Tong so nut tao ra: %d\n", total_nodes);
return 0;
}
Kết quả đầu ra
Tap la: 5 6 12 54 2 20 15 5 6 12 2 5 20 Tong so nut tao ra: 127