用贪心算法解决背包问题c语言手动输入数据

好的，背包问题是一个经典的动态规划问题。贪心算法可以用来近似解决该问题，但不一定能得到最优解。以下是使用贪心算法手动输入数据的C语言代码：

#include <stdio.h>

#define MAX_N 1000

// 物品结构体
typedef struct {
    int w; // 重量
    int v; // 价值
} Item;

// 比较函数，按照单位价值从大到小排序
int cmp(const void* a, const void* b) {
    Item* p1 = (Item*)a;
    Item* p2 = (Item*)b;
    double r1 = (double)p1->v / p1->w;
    double r2 = (double)p2->v / p2->w;
    if (r1 > r2) return -1;
    if (r1 < r2) return 1;
    return 0;
}

// 贪心算法求解背包问题
double knapsack(int n, int c, Item items[]) {
    double ans = 0;
    qsort(items, n, sizeof(Item), cmp); // 按照单位价值从大到小排序
    for (int i = 0; i < n && c > 0; i++) {
        if (c >= items[i].w) { // 如果当前物品可以完全装入背包
            ans += items[i].v;
            c -= items[i].w;
        } else { // 否则装入部分
            ans += c * ((double)items[i].v / items[i].w);
            c = 0;
        }
    }
    return ans;
}

int main() {
    int n, c;
    Item items[MAX_N];
    printf("请输入物品数量：");
    scanf("%d", &n);
    printf("请输入背包容量：");
    scanf("%d", &c);
    printf("请依次输入每个物品的重量和价值：\n");
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &items[i].w, &items[i].v);
    }
    double ans = knapsack(n, c, items);
    printf("可以获得的最大价值为：%.2f\n", ans);
    return 0;
}

在运行程序时，会先提示用户输入物品数量和背包容量，然后要求用户输入每个物品的重量和价值。程序会按照单位价值从大到小排序，然后依次将物品装入背包。最终输出可以获得的最大价值。

注意，这里的贪心算法不一定能得到最优解，因为它做出的选择仅仅是基于当前局部最优的决策。如果物品的重量和价值分布不均匀，可能会导致贪心算法得到的结果与最优解相差很大。