编辑代码

#include <stdio.h>

// 背包问题函数
int knapsack(int capacity, int weights[], int values[], int n) {
    int dp[n + 1][capacity + 1];

    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= capacity; w++) {
            if (i == 0 || w == 0)
                dp[i][w] = 0;
            else if (weights[i - 1] <= w)
                dp[i][w] = (values[i - 1] + dp[i - 1][w - weights[i - 1]]) > dp[i - 1][w] ?
                           (values[i - 1] + dp[i - 1][w - weights[i - 1]]) : dp[i - 1][w];
            else
                dp[i][w] = dp[i - 1][w];
        }
    }

    return dp[n][capacity];
}

int main() {
    
    int capacity = 50;
    int weights[] = {10, 20, 30};
    int values[] = {60, 100, 120};
    int n = sizeof(values) / sizeof(values[0]);

    // 输出结果
    printf("背包中的最大值: %d\n", knapsack(capacity, weights, values, n));

    return 0;
}