动态规划解决背包问题，使用c语言

以下是基于动态规划思想解决背包问题的 C 语言代码：

#include <stdio.h>

#define MAX_SIZE 100

// 动态规划函数，返回背包能装下的最大价值
int dynamic_knapsack(int W, int wt[], int val[], int n) {
    // 定义二维数组 dp，初始化为0
    int dp[MAX_SIZE][MAX_SIZE] = {0};

    // 依次填充二维数组 dp
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= W; j++) {
            if (wt[i-1] > j) {
                // 如果当前物品重量大于背包容量，则不放入
                dp[i][j] = dp[i-1][j];
            } else {
                // 否则，比较放入和不放入的最大价值，取较大值
                dp[i][j] = (dp[i-1][j] > dp[i-1][j-wt[i-1]] + val[i-1]) ? dp[i-1][j] : dp[i-1][j-wt[i-1]] + val[i-1];
            }
        }
    }

    return dp[n][W];
}

int main() {
    int W = 50; // 背包最大承重
    int wt[MAX_SIZE] = {10, 20, 30}; // 物品重量
    int val[MAX_SIZE] = {60, 100, 120}; // 物品价值
    int n = 3; // 物品个数

    int max_value = dynamic_knapsack(W, wt, val, n);

    printf("背包能装下的最大价值为：%d\n", max_value);

    return 0;
}

在该代码中，我们定义了一个二维数组 `dp`，并使用两个循环依次填充该数组。在填充每个元素时，我们根据动态规划方程进行判断，更新 `dp` 数组中的元素值。最终，背包能容纳的最大价值即为 `dp[n][W]`。