C语言背包问题使用性价比编写代码

在C语言中，背包问题是一个经典的动态规划问题，通常用于优化资源分配。性价比（通常指的是价值/重量比）是一种常见的决策准则，用于确定物品应放入背包还是放弃。以下是使用性价比来解决0-1背包问题的一个简单示例代码：

#include <stdio.h>

// 定义物品结构
typedef struct {
    int weight;      // 物品重量
    int value;       // 物品价值
    double ratio;    // 单位重量的价值，即性价比
} Item;

// 动态规划函数，返回最大总价值
int knapSack(int W, Item arr[], int n) {
    int dp[n + 1][W + 1]; // dp[i][j] 表示前i个物品总和能装进容量为j的最大价值

    // 初始化dp数组
    for (int i = 0; i <= n; i++) {
        dp[i] = 0;
    }
    
    for (int i = 1; i <= n; i++) { 
        for (int j = 1; j <= W; j++) {
            if (arr[i - 1].weight <= j) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - arr[i - 1].weight] + arr[i - 1].value); // 如果物品i能放入，选择放入或不放入
            } else {
                dp[i][j] = dp[i - 1][j]; // 物品i不能放入，直接使用前一个物品的情况
            }
        }
    }

    return dp[n][W];
}

// 主函数
int main() {
    int W = 50;  // 背包容量
    Item items[] = { {10, 60, 6.0}, {20, 100, 5.0}, {30, 120, 4.0} }; // 物品列表
    int n = sizeof(items) / sizeof(items);

    double max_value = knapSack(W, items, n);
    printf("最大总价值: %.2lf\n", max_value);

    return 0;
}

在这个代码中，我们首先定义了一个`Item`结构体，包含了物品的重量、价值和性价比。`knapSack`函数使用了动态规划方法，通过遍历物品并根据性价比决定是否将当前物品加入背包。最后，在`main`函数中，我们设置了一个简单的背包容量和物品列表，并计算出最大总价值。