C语言利用动态规划算法写一个实验 实验内容：假设有五个物品，重量为（2，5，4，2，3），价值为（6，3，5，4，6），购物车容量为10。利用动态规划算法求出购物车可装入物品的最大价值和装入物品。 要求:写出详细步骤并写出每个步骤相应的代码

1. 确定状态和状态转移方程

状态表示：dp[i][j]表示前i个物品装入容量为j的背包中所能获得的最大价值。

状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])，其中w[i]表示第i个物品的重量，v[i]表示第i个物品的价值。

2. 初始化

dp[0][j] = 0，dp[i][0] = 0。

3. 代码实现

#include <stdio.h>
#define N 5
#define C 10

int main()
{
    int w[N+1] = {0, 2, 5, 4, 2, 3}; // 物品重量
    int v[N+1] = {0, 6, 3, 5, 4, 6}; // 物品价值
    int dp[N+1][C+1] = {0}; // 初始值为0

    int i, j;
    for(i = 1; i <= N; i++) // 枚举物品
    {
        for(j = 1; j <= C; j++) // 枚举容量
        {
            if(j < w[i]) // 背包容量不足以装入第i个物品
                dp[i][j] = dp[i-1][j];
            else // 可以装入第i个物品，比较装与不装两种情况，取最大值
                dp[i][j] = dp[i-1][j] > dp[i-1][j-w[i]] + v[i] ? dp[i-1][j] : dp[i-1][j-w[i]] + v[i];
        }
    }

    printf("最大价值为：%d\n", dp[N][C]); // 输出最大价值

    printf("装入的物品为：");
    int res[N+1] = {0}; // 记录哪些物品被装入
    for(i = N; i >= 1; i--)
    {
        if(dp[i][C] > dp[i-1][C]) // 第i个物品被装入
        {
            res[i] = 1;
            C -= w[i];
        }
    }
    for(i = 1; i <= N; i++)
    {
        if(res[i])
            printf("%d ", i);
    }
    printf("\n");

    return 0;
}

4. 结果输出

最大价值为：15
装入的物品为：1 4 5