用C语言写一个程序，解决01背包问题，要求如下：输出为optimal value和所有的optimal solution。 输出结果格式是： The opt.val is 11\n The opt.sol(s) are: 4 2\n 4 3 1

以下是用C语言实现01背包问题的代码：

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

#define MAX_N 100
#define MAX_W 1000

int weight[MAX_N];  // 物品重量
int value[MAX_N];   // 物品价值
int opt_value;      // 最优解
int opt_sol[MAX_N]; // 最优解的方案

int dp[MAX_N][MAX_W];

// 动态规划求解01背包问题
void knapsack(int n, int W)
{
    for (int w = 0; w <= W; w++) {
        dp[0][w] = 0;
    }

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (weight[i] > w) {
                dp[i][w] = dp[i-1][w];
            } else {
                dp[i][w] = (dp[i-1][w] > dp[i-1][w-weight[i]] + value[i]) ?
                           dp[i-1][w] : dp[i-1][w-weight[i]] + value[i];
            }
        }
    }

    opt_value = dp[n][W];

    // 回溯查找最优解的方案
    int w = W;
    for (int i = n; i >= 1; i--) {
        if (opt_value == dp[i-1][w]) {
            continue;
        } else {
            opt_sol[i-1] = 1;
            w -= weight[i];
        }
    }
}

int main()
{
    int n, W;
    printf("Enter the number of items and the capacity of the knapsack: ");
    scanf("%d %d", &n, &W);

    printf("Enter the weight and value of each item:\n");
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &weight[i], &value[i]);
    }

    knapsack(n, W);

    printf("The opt.val is %d\n", opt_value);
    printf("The opt.sol(s) are:");
    for (int i = 0; i < n; i++) {
        if (opt_sol[i]) {
            printf(" %d", i+1);
        }
    }
    printf("\n");

    return 0;
}

输入格式为先输入物品个数和背包容量，再依次输入每个物品的重量和价值。输出格式为最优解的值和所有最优解的方案。