编辑代码

#include <stdio.h>

typedef struct {
    char name[20];
    int price;
    int weight;
} Item;

int maxProfit = 0;
Item items[] = {
    {"音响", 3000, 4},
    {"笔记本电脑", 2000, 3},
    {"吉他", 1500, 1}
};

void knapsack(int currentWeight, int currentProfit, int index) {
    if (currentWeight <= 4 && currentProfit > maxProfit) {
        maxProfit = currentProfit;
    }
    
    int remainingWeight = 4 - currentWeight;
    int upperBound = currentProfit;
    
    for (int i = index; i < 3; i++) {
        if (items[i].weight <= remainingWeight) {
            remainingWeight -= items[i].weight;
            upperBound += items[i].price;
        } else {
            upperBound += items[i].price * remainingWeight / items[i].weight;
            break;
        }
    }
    
    if (upperBound <= maxProfit) {
        return;
    }
    
    if (index < 3) {
        knapsack(currentWeight + items[index].weight, currentProfit + items[index].price, index + 1);
        knapsack(currentWeight, currentProfit, index + 1);
    }
}

int main() {
    knapsack(0, 0, 0);
    printf("最大利润：%d\n", maxProfit);
    return 0;
}