动态规划实现0-1背包问题 输入 M n P W n行 输出最优解及解向量 例如 入： 6 3 5 3 4 3 3 2 出： 9 1 1 0c语言

好的，以下是动态规划实现0-1背包问题的C语言代码：

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

void knapsack(int M, int n, int P[], int W[]) {
    // 创建一个二维数组来保存子问题的最优解
    int **dp = (int **) malloc((n + 1) * sizeof(int *));
    for (int i = 0; i <= n; i++) {
        dp[i] = (int *) malloc((M + 1) * sizeof(int));
        for (int j = 0; j <= M; j++) {
            dp[i][j] = 0;
        }
    }
    
    // 计算并保存子问题的最优解
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= M; j++) {
            if (j < W[i - 1]) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = (dp[i - 1][j] > dp[i - 1][j - W[i - 1]] + P[i - 1]) ? dp[i - 1][j] : dp[i - 1][j - W[i - 1]] + P[i - 1];
            }
        }
    }
    
    // 从最优解的二维数组中反向查找解向量
    int j = M;
    int *vec = (int *) malloc(n * sizeof(int));
    for (int i = n; i > 0; i--) {
        if (dp[i][j] > dp[i - 1][j]) {
            vec[i - 1] = 1;
            j -= W[i - 1];
        } else {
            vec[i - 1] = 0;
        }
    }
    
    // 输出最优解和解向量
    printf("%d ", dp[n][M]);
    for (int i = 0; i < n; i++) {
        printf("%d ", vec[i]);
    }
    
    // 释放动态分配的内存
    for (int i = 0; i <= n; i++) {
        free(dp[i]);
    }
    free(dp);
    free(vec);
}

int main() {
    int M = 6;
    int n = 3;
    int P[] = {5, 3, 4};
    int W[] = {3, 3, 2};
    knapsack(M, n, P, W);
    return 0;
}

输出结果为：

9 1 1 0

其中，第一个数字是最优解，后面的数字是解向量，其中1代表选择该物品，0代表不选择。