#include <stdio.h>
#include <stdlib.h>


typedef struct {
    int weight; // 豆子的重量
    int value;  // 豆子的价值
    double unitValue; // 豆子的单位价值
} Bean;


int compare(const void *a, const void *b) {
    return ((Bean *)b)->unitValue - ((Bean *)a)->unitValue;
}


int knapsackGreedy(Bean beans[], int n, int capacity) {
    int i;
    int totalValue = 0;


    for (i = 0; i < n; i++) {
        beans[i].unitValue = (double)beans[i].value / beans[i].weight;
    }


    qsort(beans, n, sizeof(Bean), compare);


    for (i = 0; i < n && capacity > 0; i++) {
        if (beans[i].weight <= capacity) {
            totalValue += beans[i].value;
            capacity -= beans[i].weight;
        } else {

            totalValue += (int)(beans[i].unitValue * capacity);
            capacity = 0;
        }
    }


    return totalValue;
}

int main() {
    Bean beans[] = {
        {10, 60},
        {20, 100},
        {30, 120},
        {15, 80},
        {25, 110}
    };

    int maxValue = knapsackGreedy(beans, sizeof(beans) / sizeof(beans[0]), 100);

    printf("背包中物品的总价值为：%d\n", maxValue);

    return 0;
}