用C语言栈实现背包问题

这里是一个使用 C 语言栈实现背包问题的示例代码：

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

#define MAX_SIZE 100

typedef struct {
    int weight;
    int value;
} Item;

int knapsack(Item items[], int n, int capacity) {
    int i, j, k, max_value;
    int **dp = (int **) malloc((n + 1) * sizeof(int *));
    for (i = 0; i <= n; i++) {
        dp[i] = (int *) malloc((capacity + 1) * sizeof(int));
    }
    for (i = 0; i <= n; i++) {
        dp[i][0] = 0;
    }
    for (j = 0; j <= capacity; j++) {
        dp[0][j] = 0;
    }
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= capacity; j++) {
            if (items[i - 1].weight > j) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = (dp[i - 1][j] > (dp[i - 1][j - items[i - 1].weight] + items[i - 1].value)) ?
                           dp[i - 1][j] : (dp[i - 1][j - items[i - 1].weight] + items[i - 1].value);
            }
        }
    }
    max_value = dp[n][capacity];
    i = n;
    j = capacity;
    k = 0;
    while (i > 0 && j > 0) {
        if (dp[i][j] == dp[i - 1][j]) {
            i--;
        } else {
            k++;
            i--;
            j -= items[i].weight;
        }
    }
    printf("The selected items are: ");
    for (i = k; i >= 1; i--) {
        printf("%d ", n - i + 1);
    }
    printf("\n");
    for (i = 0; i <= n; i++) {
        free(dp[i]);
    }
    free(dp);
    return max_value;
}

int main() {
    int i, n, capacity;
    Item items[MAX_SIZE];
    printf("Enter the number of items: ");
    scanf("%d", &n);
    printf("Enter the capacity of knapsack: ");
    scanf("%d", &capacity);
    printf("Enter the weight and value of each item:\n");
    for (i = 0; i < n; i++) {
        scanf("%d %d", &items[i].weight, &items[i].value);
    }
    printf("The maximum value is: %d\n", knapsack(items, n, capacity));
    return 0;
}

在这个示例中，我们首先定义了一个 `Item` 结构体，它包含了每个物品的重量和价值。然后我们实现了一个 `knapsack` 函数，它使用动态规划算法来解决背包问题。`dp[i][j]` 表示前 i 个物品放入容量为 j 的背包中所能获得的最大价值。我们先将 `dp[0][j]` 和 `dp[i][0]` 都初始化为 0，然后根据递推公式 `dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])` 来计算 `dp[i][j]`。最后，我们通过逆推得到了选中的物品，并输出它们的编号。

在 `main` 函数中，我们首先从用户输入中读取了物品数量和背包容量，然后读取每个物品的重量和价值，并调用 `knapsack` 函数来计算最大价值。