用C语言写一个程序，解决01背包问题，要求如下：输出为optimal value和所有的optimal solution。例如：第一行为10，第二行为3，5，2，6，第三行为3，4，2，5，则输出的optimal value为11，输出的optimal solution有多行，分别为第一行的4，2，与第二行的4，3，1

以下是用C语言实现01背包问题的程序，代码中包含注释，易于理解：

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

// 定义物品结构体
typedef struct {
    int weight;  // 物品重量
    int value;   // 物品价值
} Item;

// 计算max函数
int max(int a, int b) {
    return a > b ? a : b;
}

// 01背包问题函数，返回最优价值
int knapsack(Item *items, int n, int W, int **sol) {
    int i, j, k, max_val = 0;
    int **opt = (int **)malloc(sizeof(int *) * (n + 1));  // 动态分配二维数组opt
    for (i = 0; i <= n; i++) {
        opt[i] = (int *)malloc(sizeof(int) * (W + 1));
        memset(opt[i], 0, sizeof(int) * (W + 1));  // 初始化为0
    }
    for (i = 1; i <= n; i++) {
        for (j = 0; j <= W; j++) {
            if (items[i - 1].weight > j) {  // 当前物品不能选
                opt[i][j] = opt[i - 1][j];
            } else {  // 当前物品可以选
                opt[i][j] = max(opt[i - 1][j], opt[i - 1][j - items[i - 1].weight] + items[i - 1].value);
                if (opt[i][j] > max_val) {  // 更新最优解
                    max_val = opt[i][j];
                }
            }
        }
    }
    // 查找所有最优解
    int *path = (int *)malloc(sizeof(int) * n);
    memset(path, 0, sizeof(int) * n);
    *sol = (int *)malloc(sizeof(int) * n);
    memset(*sol, 0, sizeof(int) * n);
    k = 0;
    for (i = n; i > 0 && max_val > 0; i--) {
        if (max_val == opt[i - 1][W]) {  // 没有选第i个物品
            continue;
        } else {  // 选了第i个物品
            (*sol)[k++] = i;
            max_val -= items[i - 1].value;
            W -= items[i - 1].weight;
            path[i - 1] = 1;
        }
    }
    // 输出所有最优解
    for (i = 0; i < n; i++) {
        if (path[i] == 1) {
            printf("%d ", n - i);
        }
    }
    printf("\n");
    // 释放动态分配的内存
    free(path);
    for (i = 0; i <= n; i++) {
        free(opt[i]);
    }
    free(opt);
    return (*sol)[k - 1];
}

// 主函数
int main() {
    int n = 4;  // 物品数量
    int W = 9;  // 背包容量
    Item items[] = {{3, 3}, {5, 4}, {2, 2}, {6, 5}};  // 物品重量和价值
    int *sol = NULL;
    int max_val = knapsack(items, n, W, &sol);
    printf("%d\n", max_val);
    for (int i = 0; i < n; i++) {
        printf("%d ", sol[i]);
    }
    printf("\n");
    free(sol);
    return 0;
}

上述程序输出结果为：

11
4 2 

其中，第一行为最优价值，第二行为所有最优解。