编辑代码

#include <stdio.h>


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

// 动态规划实现背包问题
int knapsack(int weights[], int values[], int n, int capacity) {
    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] = max(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 weights[] = {4, 3, 1};
    int values[] = {3000, 2000, 1500};
    int capacity = 4;
    int n = sizeof(weights) / sizeof(weights[0]);

    // 计算最大价值
    int result = knapsack(weights, values, n, capacity);
    printf("最大价值: %d\n", result);

    return 0;
}