用C语言写一个程序，解决01背包问题，要求输出optimal value和所有的optimal solution

以下是用C语言实现01背包问题的代码，可以输出optimal value和所有的optimal solution：

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

int n, W, w[100], v[100];
int opt[101][1001] = {0};   // opt[i][j]表示前i个物品，容量为j时的最优值
int sol[101][1001] = {0};   // sol[i][j]表示前i个物品，容量为j时的最优方案数

int max(int a, int b)
{
    return a > b ? a : b;
}

void knapsack()
{
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=W; j++) {
            if (w[i] > j) {
                opt[i][j] = opt[i-1][j];
            } else {
                opt[i][j] = max(opt[i-1][j], opt[i-1][j-w[i]] + v[i]);
            }
        }
    }

    for (int i=1; i<=n; i++) {
        for (int j=1; j<=W; j++) {
            if (opt[i][j] == opt[i-1][j]) {
                sol[i][j] += sol[i-1][j];
            }
            if (j >= w[i] && opt[i][j] == opt[i-1][j-w[i]] + v[i]) {
                sol[i][j] += sol[i-1][j-w[i]];
            }
            if (opt[i][j] == opt[n][W]) {
                printf("Optimal solution: ");
                for (int k=1; k<=i; k++) {
                    if (j >= w[k] && opt[i][j] == opt[i-1][j-w[k]] + v[k]) {
                        printf("%d ", k);
                    }
                }
                printf("\n");
            }
        }
    }
}

int main()
{
    printf("Enter the number of items and the capacity of the knapsack: ");
    scanf("%d %d", &n, &W);
    printf("Enter the weights and values of the items:\n");
    for (int i=1; i<=n; i++) {
        scanf("%d %d", &w[i], &v[i]);
        sol[i][0] = 1;
    }

    knapsack();

    printf("Optimal value: %d\n", opt[n][W]);

    return 0;
}

在上面的代码中，我们使用了两个二维数组opt和sol来分别存储最优值和最优方案数。在计算opt数组时，我们使用了动态规划的思想，通过填表来求解。在计算sol数组时，我们沿用了opt数组的计算方法，在计算过程中，如果当前位置的值等于opt[n][W]，则说明找到了一个optimal solution，我们就可以输出对应的物品编号。最后再输出optimal value即可。