背包问题c语言

背包问题是一种经典的动态规划问题，可以用C语言来实现。以下是一种基于动态规划思想的背包问题的C语言实现：

#include<stdio.h>
#define MAX_N 100
#define MAX_W 1000

int n, W;
int w[MAX_N], v[MAX_N];
int dp[MAX_N+1][MAX_W+1];

int main() {
    scanf("%d%d", &n, &W);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &w[i], &v[i]);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= W; j++) {
            if (j < w[i]) {
                dp[i+1][j] = dp[i][j];
            } else {
                dp[i+1][j] = dp[i][j] > dp[i][j-w[i]]+v[i] ? dp[i][j] : dp[i][j-w[i]]+v[i];
            }
        }
    }
    printf("%d\n", dp[n][W]);
    return 0;
}

在这段代码中，我们首先定义了一个二维数组`dp`，用于存储每个状态下的最大价值。其中，`dp[i][j]`表示前`i`个物品中，不超过重量`j`的最大价值。接下来，我们用两个循环遍历每个状态，根据动态转移方程来更新`dp[i+1][j]`的值，最后输出`dp[n][W]`即可得到最终结果。

需要注意的是，这里的动态转移方程为：

dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])

即将第`i`个物品放入背包或不放入背包两种情况中选取最大值。同时，我们需要注意数组下标从0开始，因此在更新`dp[i+1][j]`的值时，需要使用`dp[i][j]`和`dp[i][j-w[i]]`来更新。