回溯法解决01背包问题，用c语言

回溯法是一种通过穷举所有可能性来解决问题的搜索算法，特别适用于那些存在多个解决方案的问题，如背包问题。对于01背包问题，每个物品都有一个价值和重量，目标是在不超过背包容量的前提下，选择物品以最大化总价值。

在C语言中使用回溯法解决01背包问题的主要步骤如下：

1. 定义状态：表示当前背包是否能装下第i个物品及其对总价值的影响。通常用一个二维数组dp[i][w]记录，其中i是物品编号，w是当前背包剩余容量。

2. 初始化：设置基本情况，当背包为空（w=0）或物品不存在（i=0）时，价值为0。

3. 搜索函数：对于每个物品，有两种选择：放入背包（值+dp[i-1][w-w_i]）或不放（值+dp[i-1][w]）。遍历这两种情况，然后递归地尝试下一个物品。

4. 回溯：如果发现当前状态下背包的价值小于之前找到的最大价值，就回溯到上一步，尝试另一种选择。

5. 返回结果：当所有物品都考虑过后，找到的最大价值就是最终解。

#include <stdio.h>

int knapsack(int W, int wt[], int val[], int n) {
    int i, w;
    int dp[n + 1][W + 1];

    // Base cases
    for (i = 0; i <= n; i++) {
        dp[i][0] = 0;
    }
    for (w = 1; w <= W; w++) {
        dp[0][w] = 0;
    }

    // Fill the dp table
    for (i = 1; i <= n; i++) {
        for (w = 1; w <= W; w++) {
            if (wt[i - 1] <= w) {
                dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[n][W];
}

int main() {
    int W = 50, wt[] = {10, 20, 30}, val[] = {60, 100, 120};
    int n = sizeof(wt) / sizeof(wt[0]);

    printf("Maximum value that can be put in a bag of capacity %d is %d\n", W, knapsack(W, wt, val, n));

    return 0;
}