编辑代码

#include <stdio.h>

// 定义最大物品数量和背包容量
#define MAX_ITEMS 100
#define MAX_CAPACITY 1000

// 动态规划解决背包问题
int knapsack(int values[], int weights[], int n, int capacity) {
    // 创建一个二维数组用于存储子问题的解
    int dp[MAX_ITEMS + 1][MAX_CAPACITY + 1];
    
    // 初始化边界条件
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 0;
    }
    for (int j = 0; j <= capacity; j++) {
        dp[0][j] = 0;
    }
    
    // 动态规划求解
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= capacity; j++) {
            // 如果当前物品重量大于背包容量，则不放入背包
            if (weights[i - 1] > j) {
                dp[i][j] = dp[i - 1][j];
            }
            // 否则，选择放入或不放入背包，取价值最大的方案
            else {
                dp[i][j] = (dp[i - 1][j] > (dp[i - 1][j - weights[i - 1]] + values[i - 1])) ? dp[i - 1][j] : (dp[i - 1][j - weights[i - 1]] + values[i - 1]);
            }
        }
    }
    
    // 返回最优解
    return dp[n][capacity];
}

int main() {
    int values[] = {90, 135, 270}; // 物品价值
    int weights[] = {25, 30, 15}; // 物品重量
    int n = sizeof(values) / sizeof(values[0]); // 物品数量
    int capacity = 50; // 背包容量
    
    int max_value = knapsack(values, weights, n, capacity);
    
    printf("可以获得的最大值是: %d\n", max_value);
    
    return 0;
}