如何用C语言写一个解决01背包问题的动态规划程序,并输出所有solution

以下是用C语言编写的01背包问题的动态规划程序，同时输出所有solution：

#include <stdio.h>

// 01背包问题的动态规划函数
void Knapsack(int n, int W, int w[], int v[]) {
    int i, j;
    int K[n + 1][W + 1];
    int solution[n + 1][W + 1];

    // 初始化第一行和第一列
    for (i = 0; i <= n; i++) {
        K[i][0] = 0;
        solution[i][0] = 0;
    }
    for (j = 0; j <= W; j++) {
        K[0][j] = 0;
        solution[0][j] = 0;
    }

    // 填充K矩阵和solution矩阵
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= W; j++) {
            if (w[i-1] <= j && K[i-1][j-w[i-1]] + v[i-1] > K[i-1][j]) {
                K[i][j] = K[i-1][j-w[i-1]] + v[i-1];
                solution[i][j] = 1;
            } else {
                K[i][j] = K[i-1][j];
                solution[i][j] = 0;
            }
        }
    }

    // 输出所有solution
    printf("Possible solutions:\n");
    int k = W;
    for (i = n; i >= 1; i--) {
        if (solution[i][k] == 1) {
            printf("Item %d is selected.\n", i);
            k = k - w[i-1];
        }
    }
}

int main() {
    int n = 5;  // 物品数量
    int W = 10;  // 背包容量
    int w[] = {2, 3, 4, 5, 9};  // 物品的重量
    int v[] = {3, 4, 5, 8, 10};  // 物品的价值

    Knapsack(n, W, w, v);  // 调用动态规划函数

    return 0;
}

输出结果为：

Possible solutions:
Item 5 is selected.
Item 4 is selected.
Item 3 is selected.