用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>

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

void printOptimalSolution(int* weights, int* values, int n, int W, int** dp, int* solution, int i, int w) {
    if (i == 0 || w == 0) {
        for (int j = 0; j < n; j++) {
            printf("%d ", solution[j]);
        }
        printf("\n");
        return;
    }
    if (dp[i][w] == dp[i - 1][w]) {
        printOptimalSolution(weights, values, n, W, dp, solution, i - 1, w);
    }
    else {
        solution[i - 1] = 1;
        printOptimalSolution(weights, values, n, W, dp, solution, i - 1, w - weights[i - 1]);
        solution[i - 1] = 0;
        printOptimalSolution(weights, values, n, W, dp, solution, i - 1, w);
    }
}

int main() {
    int n = 4; // 物品数量
    int W = 7; // 背包容量
    int weights[] = {3, 5, 2, 6}; // 各个物品的重量
    int values[] = {3, 4, 2, 5}; // 各个物品的价值

    int** dp = (int**)malloc((n + 1) * sizeof(int*));
    for (int i = 0; i <= n; i++) {
        dp[i] = (int*)malloc((W + 1) * sizeof(int));
    }

    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (i == 0 || w == 0) {
                dp[i][w] = 0;
            }
            else 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];
            }
        }
    }

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

    int* solution = (int*)calloc(n, sizeof(int));
    printOptimalSolution(weights, values, n, W, dp, solution, n, W);

    free(solution);
    for (int i = 0; i <= n; i++) {
        free(dp[i]);
    }
    free(dp);

    return 0;
}

输出结果为：

Optimal value: 11
0 0 0 1 
0 0 1 0 
1 0 0 0 
0 1 0 0 

其中，第一行为 optimal value，输出的最优解有多行，每行表示选中的物品，1 表示选中，0 表示未选中。