用动态规划实现0-1背包问题c语言

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

#include <stdio.h>

#define MAX_N 100   // 物品数量的最大值
#define MAX_W 1000  // 背包容量的最大值

int n;              // 物品数量
int w[MAX_N];       // 物品重量
int v[MAX_N];       // 物品价值
int dp[MAX_N+1][MAX_W+1];    // DP 数组

int main()
{
    // 读入物品数量和背包容量
    int W;
    scanf("%d %d", &n, &W);

    // 读入物品重量和价值
    for (int i = 0; i < n; i++)
        scanf("%d %d", &w[i], &v[i]);

    // 初始化 DP 数组
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= W; j++)
            dp[i][j] = 0;

    // 动态规划求解
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= W; j++)
        {
            if (j >= w[i-1])
                dp[i][j] = (dp[i-1][j-w[i-1]] + v[i-1] > dp[i-1][j]) ? dp[i-1][j-w[i-1]] + v[i-1] : dp[i-1][j];
            else
                dp[i][j] = dp[i-1][j];
        }
    }

    // 输出结果
    printf("%d\n", dp[n][W]);

    return 0;
}

代码的思路是：使用一个二维数组 `dp[i][j]` 表示前 `i` 个物品放入容量为 `j` 的背包中所能获得的最大价值。那么状态转移方程为：

- 如果第 `i` 个物品放入背包中，那么最大价值为 `dp[i-1][j-w[i-1]] + v[i-1]`；
- 如果第 `i` 个物品不放入背包中，那么最大价值为 `dp[i-1][j]`。

最后的结果就是 `dp[n][W]`。