编辑代码

#include <stdio.h>
#define N 5  // 物品数量
#define W 10  // 背包容量

int max(int a, int b) {
    return a > b ? a : b;
}

int knapsack(int weights[], int values[]) {
    int i, w;
    int dp[N+1][W+1];  // 动态规划表格，dp[i][w]表示前i个物品放入容量为w的背包中所获得的最大价值

    // 初始化动态规划表格
    for (i = 0; i <= N; i++) {
        dp[i][0] = 0;
    }
    for (w = 0; w <= W; w++) {
        dp[0][w] = 0;
    }

    // 填充动态规划表格
    for (i = 1; i <= N; i++) {
        for (w = 1; w <= W; w++) {
            if (weights[i-1] <= w) {
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1]);
            }
            else {
                dp[i][w] = dp[i-1][w];
            }
        }
    }

    // 返回最终结果
    return dp[N][W];
}

int main() {
    int weights[N] = {2, 3, 4, 5, 9};  // 物品重量数组
    int values[N] = {3, 4, 5, 6, 10};  // 物品价值数组
    int max_value;

    max_value = knapsack(weights, values);

    printf("背包容量为%d，物品数量为%d，最大价值为%d\n", W, N, max_value);
    return 0;
}