C语言动态规划算法解0-1背包问题 • 程序要求 • 动态规划的过程必须通过 DProcessing( wi , vi , m[i,j] ) 计算 • wi 表示物品 i 的重量， • vi 代表物品 i 的价值， • m[ i, j ] 代表当前正在规划的 重量为 j 的背包 的价值 • 注：动态规划的过程禁止直接写在主函数中！

以下是一份 C 语言动态规划算法解 0-1 背包问题的示例代码：

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

// DProcessing 函数用于计算动态规划的过程
void DProcessing(int *w, int *v, int n, int m, int **mTable)
{
    // 初始化第 0 行和第 0 列
    for (int i = 0; i <= n; i++)
    {
        mTable[i][0] = 0;
    }
    for (int j = 0; j <= m; j++)
    {
        mTable[0][j] = 0;
    }

    // 开始动态规划
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (w[i] > j)
            {
                mTable[i][j] = mTable[i - 1][j];
            }
            else
            {
                int value1 = mTable[i - 1][j];
                int value2 = mTable[i - 1][j - w[i]] + v[i];
                mTable[i][j] = (value1 > value2) ? value1 : value2;
            }
        }
    }
}

int main()
{
    int n = 5;          // 物品数量
    int m = 10;         // 背包容量
    int w[] = {0, 2, 2, 6, 5, 4};  // 物品重量，前面加0是为了方便计算
    int v[] = {0, 6, 3, 5, 4, 6};  // 物品价值，前面加0是为了方便计算

    // 动态分配二维数组
    int **mTable = (int **)malloc((n + 1) * sizeof(int *));
    for (int i = 0; i <= n; i++)
    {
        mTable[i] = (int *)malloc((m + 1) * sizeof(int));
    }

    // 调用 DProcessing 函数计算动态规划过程
    DProcessing(w, v, n, m, mTable);

    // 输出最大价值
    printf("The maximum value is %d\n", mTable[n][m]);

    // 释放动态分配的内存
    for (int i = 0; i <= n; i++)
    {
        free(mTable[i]);
    }
    free(mTable);

    return 0;
}

动态规划的过程被封装在了 DProcessing 函数中，函数的参数包括物品重量数组 w、物品价值数组 v、物品数量 n、背包容量 m，以及一个二维数组 mTable 用于存储动态规划的结果。在主函数中，我们只需要定义好物品数量、背包容量、物品重量和价值数组，然后分配好动态规划结果存储的内存，调用 DProcessing 函数即可。最后输出动态规划的结果，再释放动态分配的内存。