算法背包问题C语言

背包问题是一个经典的动态规划问题，可以用C语言来实现。

背包问题的描述：有一个背包可以装载一定重量的物品，现在有n个物品，每个物品的重量和价值不同。要求在不超过背包容量的前提下，选择一些物品，使得它们的总价值最大。

实现思路：

1. 定义一个二维数组dp[i][j]表示前i个物品中，背包容量为j时的最大价值。

2. 初始化dp数组，当i=0或j=0时，dp[i][j]=0。

3. 对于每个物品i，遍历所有的背包容量j，根据以下公式更新dp数组：

- 如果j < weight[i]，则dp[i][j] = dp[i-1][j]，即当前物品无法放入背包中，最大价值为前i-1个物品中容量为j时的最大价值。

- 如果j >= weight[i]，则dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])，即当前物品可以放入背包中，最大价值为前i-1个物品中容量为j时的最大价值和当前物品价值之和，或者前i-1个物品中容量为j-weight[i]时的最大价值和当前物品价值之和的较大值。

4. 最终dp[n][m]即为前n个物品中，背包容量为m时的最大价值。

以下是实现代码：

#include <stdio.h>
#define max(a, b) ((a) > (b) ? (a) : (b))

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    int weight[n+1], value[n+1];
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &weight[i], &value[i]);
    }

    int dp[n+1][m+1];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            } else if (j < weight[i]) {
                dp[i][j] = dp[i-1][j];
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]);
            }
        }
    }

    printf("%d\n", dp[n][m]);
    return 0;
}