动态规划写背包问题c语言代码以及伪代码

好的，这是一道经典的背包问题，下面是 C 语言代码和伪代码实现：

C 语言代码实现：

#include <stdio.h>
#include <stdlib.h>
#define MAX_N 100000
 
int dp[MAX_N + 1][2]; // dp[i][0/1] 表示用前 i 个物品时背包容量为 j 时的最大价值
int w[MAX_N], v[MAX_N]; // w[i]/v[i] 表示第 i 件物品的重量和价值
 
int main()
{
    int n, m; // n 个物品，背包容量为 m
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &w[i], &v[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (j < w[i])
            {
                dp[i][j % 2] = dp[i - 1][j % 2];
            }
            else
            {
                int choose = dp[i - 1][(j - w[i]) % 2] + v[i]; // 选择第 i 个物品
                int not_choose = dp[i - 1][j % 2]; // 不选择第 i 个物品
                dp[i][j % 2] = (choose > not_choose) ? choose : not_choose;
            }
        }
    }
    printf("%d\n", dp[n][m % 2]); // 输出最大价值
    return 0;
}

伪代码实现：

n: 物品数量
m: 背包容量
w[i]: 第 i 件物品的重量
v[i]: 第 i 件物品的价值

dp[n+1][2] // n 个物品时背包容量为 j 时的最大价值
for j in range(1, m+1):
    dp[0][j % 2] = 0

for i in range(1, n+1):
    for j in range(1, m+1):
        if j < w[i]:
            dp[i][j % 2] = dp[i-1][j % 2]
        else:
            choose = dp[i-1][(j-w[i]) % 2] + v[i]
            not_choose = dp[i-1][j % 2]
            dp[i][j % 2] = max(choose, not_choose)

Output: dp[n][m % 2]