编辑代码

#include <stdio.h>

#define MAX_ITEMS 100
#define MAX_CAPACITY 100

typedef struct {
    int weight;
    int value;
} Item;

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

int bound(int i, int weight, int value, Item items[], int n, int capacity) {
    while (i < n && weight + items[i].weight <= capacity) {
        weight += items[i].weight;
        value += items[i].value;
        i++;
    }

    if (i < n)
        value += (capacity - weight) * items[i].value / items[i].weight;

    return value;
}

int knapsack(Item items[], int n, int capacity) {
    int max_value = 0;
    int weight = 0, value = 0;
    int i = 0;

    while (1) {
        if (weight + items[i].weight <= capacity) {
            weight += items[i].weight;
            value += items[i].value;
        } else {
            int temp_value = bound(i + 1, weight, value, items, n, capacity);
            max_value = max(max_value, value + temp_value);
        }

        i++;

        if (i >= n)
            break;
    }

    return max_value;
}

int main() {
    int n, capacity;
    printf("Enter number of items: ");
    scanf("%d", &n);

    Item items[MAX_ITEMS];

    printf("Enter weights and values of items:\n");
    for (int i = 0; i < n; i++)
        scanf("%d %d", &items[i].weight, &items[i].value);

    printf("Enter the capacity of the knapsack: ");
    scanf("%d", &capacity);

    int max_value = knapsack(items, n, capacity);
    printf("The maximum value that can be obtained is: %d\n", max_value);

    return 0;
}