您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> 關於C語言

C語言實戰：用回溯法解決經典背包問題

編輯：關於C語言

前言

背包問題是數據結構與演算法中的經典命題。近日在鑽研 C 語言堆棧空間管理時，重溫了這道題目，決定用回溯法配合堆疊結構完整實現一遍。本文將從問題描述、演算法思路、關鍵代碼解析三個維度，帶你走進「裝滿背包」的邏輯世界。

問題描述

給定一個總容量為 T 的背包，以及 n 件體積分別為 w1, w2, ..., wn 的物品。要求從中挑選若干件物品，使其體積總和恰好等於 T，並找出所有滿足條件的組合。

例如：T = 10，物品體積集合 {1, 8, 4, 3, 5, 2} 時，可得 4 組解：

(1, 4, 3, 2)
(1, 4, 5)
(8, 2)
(3, 5, 2)

演算法思路：回溯法 + 堆疊

回溯法的核心是「試錯」與「回退」：

將物品排成一列，順序嘗試裝入背包。
若裝入第 i 件後未滿，繼續嘗試第 i+1 件。
若某件物品「太大」無法裝入，捨棄它，嘗試下一件。
若剩餘物品無法填滿背包，說明「剛裝入的那件不合適」，將其取出（回溯），改從它之後的物品中選取。
重複上述過程，直到找到所有解或確認無解。

因為回溯遵循「後進先出」原則，自然需要用到堆疊來記錄當前路徑。

關鍵代碼解析

以下為核心求解函數 solution() 的邏輯重點（完整代碼見文末）：

1. 動態申請堆疊空間

int *stack = (int *)malloc(size * sizeof(int));
int *header = stack; // 保存堆疊首地址，便於最後釋放

2. 外層循環：以每個物品為起點

for (i = 0; i < size; i++) {
    stack = header; // 每輪重置堆疊指針
    j = 0;          // 堆疊當前深度
    temp.i = temp.sum = 0; // 重置索引與累加和
    // ...

3. 內層循環：嘗試裝入後續物品

while (temp.i <= size - i) {
    j++;
    temp.sum += *(source + i + temp.i); // 累加體積
    *stack = *(source + i + temp.i);    // 入棧
    stack++;

    if (temp.sum == volume) { // 找到一組解
        // 彈棧輸出
        while (j > 0) {
            printf("%d ", *(stack - 1));
            j--; stack--;
        }
        putchar('\n');
    }
    else if (temp.sum < volume) { // 未滿，繼續拿下一件
        temp.i++;
        continue;
    }
    else { // 超重，回溯：彈棧、減和、嘗試下一件
        temp.sum -= *(source + i + temp.i);
        temp.i++;
        *stack = 0; // 清理棧頂
        j--; stack--;
        continue;
    }
}

4. 記憶體釋放

free(stack);
free(header); // 實際上只需 free(header)，此處雙重釋放有風險，建議修正

主程式流程

輸入物品數量 size 並動態分配陣列 number。
輸入各物品體積。
輸入背包容量 volume。
呼叫 solution(number, volume, size) 求解並輸出所有組合。

完整代碼

#include <stdio.h>
#include <stdlib.h>

struct node { int sum; int i; };
typedef struct node NODE;

int getmemory(int **p, int size) {
    if (size <= 0) return 0;
    *p = (int *)malloc(size * sizeof(int));
    return *p != NULL;
}

int assignvalue(int *dest, int size) {
    if (!dest) return 0;
    while (size--) scanf("%d", dest++);
    return 1;
}

int solution(int *source, int volume, int size) {
    int i, j;
    int *stack, *header;
    NODE temp;
    if (!source || volume == 0 || size == 0) return 0;
    if (!(stack = (int *)malloc(size * sizeof(int)))) return 0;
    header = stack;

    for (i = 0; i < size; i++) {
        stack = header; j = 0; temp.i = temp.sum = 0;
        while (temp.i <= size - i) {
            j++;
            temp.sum += *(source + i + temp.i);
            *stack = *(source + i + temp.i);
            stack++;
            if (temp.sum == volume) {
                while (j > 0) { printf("%d ", *(stack - 1)); j--; stack--; }
                putchar('\n');
            }
            if (temp.sum < volume) { temp.i++; continue; }
            if (temp.sum > volume) {
                temp.sum -= *(source + i + temp.i);
                temp.i++; *stack = 0; j--; stack--; continue;
            }
        }
    }
    free(header); // 修正：只釋放首地址
    return 1;
}

int main() {
    int size, volume, *number = NULL;
    printf("input the total number of items: ");
    scanf("%d", &size);
    printf("\nEnter the volumes:\n");
    if (!getmemory(&number, size)) exit(1);
    if (!assignvalue(number, size)) exit(1);
    puts("\nPlease enter the volume of the package:");
    scanf("%d", &volume);
    if (!solution(number, volume, size)) exit(1);
    free(number);
    return 0;
}