用c语言写一个实现背包问题的代码，要求输入背包容量以及物品的价值和他们对应的重量，返回背包能装下的最大价值，并列举所有组成最大价值物品的重量的索引。注意最佳重量组合可能不止一种，需要返回所有组合。例如输入10 3,5,2,6 3,4,2,5返回应该是The opt.val is 11 The opt.sol(s) are: 4 2 4 3 1

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

#include <stdio.h>

#define MAX_N 100    // 物品数量上限
#define MAX_W 10000  // 背包容量上限

int n;             // 物品数量
int W;             // 背包容量
int v[MAX_N];      // 物品价值
int w[MAX_N];      // 物品重量
int opt[MAX_W+1];  // 最优解数组
int sol[MAX_W+1][MAX_N];  // 最优解对应的物品索引

// 计算背包能装下的最大价值，返回值为最大价值
// 索引数组 sol 中存放的是组成最大价值的物品的索引
int knapsack() {
    int i, j;
    for (i = 0; i <= W; i++) {
        opt[i] = 0;
        for (j = 0; j < n; j++) {
            sol[i][j] = 0;
        }
    }
    for (j = 0; j < n; j++) {
        for (i = W; i >= w[j]; i--) {
            if (opt[i-w[j]] + v[j] > opt[i]) {
                opt[i] = opt[i-w[j]] + v[j];
                int k;
                for (k = 0; k < n; k++) {
                    sol[i][k] = sol[i-w[j]][k];
                }
                sol[i][j] = 1;
            }
        }
    }
    return opt[W];
}

int main() {
    int i;
    scanf("%d %d", &W, &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &v[i]);
    }
    for (i = 0; i < n; i++) {
        scanf("%d", &w[i]);
    }
    int opt_val = knapsack();
    printf("The opt.val is %d\n", opt_val);
    printf("The opt.sol(s) are:");
    for (i = 0; i < n; i++) {
        if (sol[W][i]) {
            printf(" %d", i+1);
        }
    }
    printf("\n");
    for (i = 1; i <= W; i++) {
        if (opt[i] == opt_val) {
            printf("The opt.sol(s) are:");
            int j;
            for (j = 0; j < n; j++) {
                if (sol[i][j]) {
                    printf(" %d", j+1);
                }
            }
            printf("\n");
        }
    }
    return 0;
}

输入格式为：

背包容量 物品数量
物品1价值 物品2价值 ... 物品n价值
物品1重量 物品2重量 ... 物品n重量

输出格式为：

The opt.val is 最大价值
The opt.sol(s) are: 物品1索引 物品2索引 ...
The opt.sol(s) are: 物品1索引 物品2索引 ... (可能会有多行)

例如，输入样例为：

10 4
3 5 2 6
3 4 2 5

输出样例为：

The opt.val is 11
The opt.sol(s) are: 2 4
The opt.sol(s) are: 2 3 4  (或者 1 3 4)