01背包回溯算法c语言

01背包（Knapsack Problem with 0 and 1）是一种经典的动态规划问题，常用于计算机科学的算法分析。在C语言中，可以使用回溯法（Backtracking）来解决此问题，当物品的价值和重量有限制时，求解如何选择物品使得总价值最大。以下是基本的回溯算法流程：

1. 定义状态：设`dp[i][w]`表示前i个物品中选取总重量不超过w的最大价值。

2. 初始化：对于每个物品，如果它的重量大于当前背包剩余容量，则其价值为0；否则，将它加入背包的情况和不加入的情况分别计算并取较大值作为当前状态下的最大价值。

3. 回溯函数：从最后一个物品开始，依次尝试将每个物品放入背包，若放入则更新dp值，并递归考虑下一个物品。如果某次尝试导致超重，则回溯到上一步，移除该物品，继续尝试其他物品。

4. 结束条件：当所有物品都尝试过后，dp数组的`dp[n][W]`即为最大价值，其中n是物品数量，W是背包容量。

#include <stdio.h>

// 假设values[]存储物品价值，weights[]存储物品重量，capacity是背包容量
int knapSack(int W, int weights[], int values[], int n) {
    int dp[n + 1][W + 1];
    
    // 初始化为0
    for (int i = 0; i <= n; ++i)
        for (int w = 0; w <= W; ++w)
            dp[i][w] = 0;

    for (int i = 1; i <= n; ++i) {
        for (int w = 1; w <= W; ++w) {
            if (weights[i - 1] <= w) { // 物品能完全放入背包
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w]; // 物品无法放入，直接取上一层的最优值
            }
        }
    }

    return dp[n][W];
}

// 辅助函数，返回两个数的最大值
int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int values[] = {60, 100, 120};
    int weights[] = {10, 20, 30};
    int capacity = 50;
    int n = sizeof(values) / sizeof(values[0]);

    printf("The maximum value in the knapsack is %d\n", knapSack(capacity, weights, values, n));

    return 0;
}