發現子集和遞歸地產生不正確的輸出

Question

跟隨this method (pdf)來實現一個遞歸解決方案，但我認爲它是越野車。我已經完全按照pdf文件中的描述實施它。

下面的代碼的輸出是錯誤的。它顯示了目標位置。目標數組包含應該添加以獲得總和的數字的比特表示。

將binary[i] = 1置於else if條件可以修復問題，但它沒有任何意義。

有沒有可能澄清什麼是正確的解決方案？

#define SIZE(a) sizeof(a)/sizeof(a[0]) 
int binary[100]; 
void foo(int target, int i, int sum, int *a, int size) { 
    binary[i] = 1; 
    if (target == sum+a[i]) { 
     int j; 
     for (j=0;j<size;j++) 
      printf("%d\n", binary[j]); 
     return; 
    } else if ((i+1 < size) && (sum + a[i] < target)) { 
     foo(target, i+1, sum + a[i], a, size); 
    } 
    if ((i+1 < size) && (sum +a[i+1] <= target)) { 
     binary[i] = 0; 
     foo(target, i+1, sum, a, size); 
    } 
} 

int main() 
{ 
    int i, target =10,a[] = {1, 2, 3, 5, 100}; 
    foo(target, 0, 0, a, SIZE(a)); 
} 

電流輸出：0 1 1 1 1

預期輸出：0 1 1 1 0

Answer 1

#include <stdio.h> 

#define SIZE(a) sizeof(a)/sizeof(a[0]) 
int binary[100]; 

void show(int* p, int size) { 
    int j; 
    for (j = 0; j < size; j++) 
     printf("%d\n", p[j]); 
} 

void foo(int target, int i, int sum, int *a, int size) { 
    if (sum == target) { 
     // solution found 
     show(binary, size); 
    } else if (sum < target && i < size) { 
     // try both branches 
     // 1. current value used 
     binary[i] = 1; 
     foo(target, i + 1, sum + a[i], a, size); 
     // 2. current value skipped 
     binary[i] = 0; 
     foo(target, i + 1, sum, a, size); 
    } else { 
     // no solution on this path 
    } 
} 

int main() { 
    int target = 10; 
    int a[] = {1, 2, 3, 5, 100}; 
    foo(target, 0, 0, a, SIZE(a)); 
} 

說明：

• 讓我們只說大約i，sum和binary，因爲一切是從這個常數算法'透視。
• 我們的目標是從a中選擇個別元素，其總和等於target。當我們達到這種情況時，我們就完成了，我們唯一的工作就是解決方案show。
• 只有當我們當前的sum仍然低於target時，該算法纔可以繼續，並且我們還沒有達到a的末尾。
• 總有兩種可能：使用當前元素或跳過它。兩者都是遞歸調查的。
• 該程序必須在binary的適當位置保留零，否則將在backtracking的各個級別提供令人誤解的結果。爲此，使用分支機構首先進行調查。