编辑代码

// 定义表示物品的数据结构
struct Item {
    int weight;
    int value;
};

// 定义全局变量用于存储最优解
int maxProfit = 0;

// 分支界限法算法
void branchAndBound(int capacity, int currentProfit, int level, struct Item items[], int n) {
    if (level == n) {
        if (currentProfit > maxProfit) {
            maxProfit = currentProfit;
        }
        return;
    }
    
    // 不选择当前物品
    branchAndBound(capacity, currentProfit, level + 1, items, n);
    
    // 选择当前物品
    if (capacity >= items[level].weight) {
        branchAndBound(capacity - items[level].weight, currentProfit + items[level].value, level + 1, items, n);
    }
}

// 测试函数
int main() {
    struct Item items[] = {{10, 60}, {20, 100}, {30, 120}};  // 示例物品
    int capacity = 50;  // 背包容量
    int n = sizeof(items) / sizeof(items[0]);  // 物品数量
    
    branchAndBound(capacity, 0, 0, items, n);  // 调用分支界限法算法
    
    printf("最大总价值为: %d\n", maxProfit);  // 输出最大总价值
    
    return 0;
}