c++实现分支限界法解决0-1背包问题

在C++中，我们可以使用分支限界算法（Branch and Bound）来解决0-1背包问题。这个问题是一个经典的动态规划问题，通常我们不会直接使用`vector`库，而是手动管理数组或列表。这里我将演示一个基本的实现，假设我们已经定义了物品数组`items`，其中存储了每个物品的价值`values`和重量`weights`。 ```cpp #include <iostream> #include <climits> // 使用INT_MAX作为上限 const int MAX_ITEMS = 100; // 设置最大物品数 int values[MAX_ITEMS], weights[MAX_ITEMS]; // 物品价值和重量 void branchAndBound(int capacity, bool* chosen) { int totalValue = 0; std::function<void(int, bool*)> backtrack = [&](int index, bool* chosen) { if (index == MAX_ITEMS || totalValue + values[index] > capacity) { return; // 如果已达到容量限制，或者无法增加更多价值，回溯 } // 选择物品 chosen[index] = true; totalValue += values[index]; backtrack(index + 1, chosen); // 继续下一个物品 // 不选择物品 chosen[index] = false; if (totalValue > capacity * chosen[index]) { backtrack(index + 1, chosen); // 因为之前选择导致总值超过，需要尝试其他路径 } else { // 如果当前选择更好，保留结果 } }; backtrack(0, chosen); } int main() { int n; // 输入物品数量 std::cout << "Enter the number of items: "; std::cin >> n; for (int i = 0; i < n; ++i) { std::cout << "Enter value and weight for item " << i+1 << ": "; std::cin >> values[i] >> weights[i]; } int capacity; std::cout << "Enter the bag capacity: "; std::cin >> capacity; bool chosen[MAX_ITEMS] = {false}; // 初始化所有物品未选中 branchAndBound(capacity, chosen); std::cout << "The maximum value that can be carried is: " << totalValue << "\n"; std::cout << "Items selected: \n"; for (int i = 0; i < n; ++i) { if (chosen[i]) { std::cout << "Item " << i+1 << " with value " << values[i] << " and weight " << weights[i] << "\n"; } } return 0; } ``` 在这个程序中，用户会输入物品的数量、每个物品的价值和重量，以及背包的容量。然后`branchAndBound`函数会递归地尝试所有可能的选择组合，并通过比较当前解决方案和最优解来决定是否继续分支。

以下是使用先进先出队列式分支限界法求解0-1背包问题的完整C代码： ``` #include<stdio.h> #include<stdlib.h> #define MAX_SIZE 100 //物品结构体 typedef struct _item{ int weight; //重量 int value; //价值 int bound; //价值上界 }Item; //结点结构体 typedef struct _node{ int level; //决策树层数 int profit; //当前已获得的价值 int weight; //当前已占用的重量 int bound; //价值上界 int select[MAX_SIZE]; //选择情况 }Node; //队列结构体 typedef struct _queue{ Node elem[MAX_SIZE]; //队列元素 int front; //队头指针 int rear; //队尾指针 }Queue; //初始化队列 void initQueue(Queue *q){ q->front = q->rear = 0; } //判断队列是否为空 int isEmpty(Queue *q){ if(q->front == q->rear) return 1; else return 0; } //进队列 void enqueue(Queue *q, Node n){ if((q->rear+1)%MAX_SIZE == q->front){ printf("Queue is full!\n"); exit(1); } q->elem[q->rear] = n; q->rear = (q->rear+1)%MAX_SIZE; } //出队列 Node dequeue(Queue *q){ if(isEmpty(q)){ printf("Queue is empty!\n"); exit(1); } Node n = q->elem[q->front]; q->front = (q->front+1)%MAX_SIZE; return n; } //计算结点的价值上界 int bound(Node n, int nItems, Item items[]){ int j, k; int totalWeight; int boundValue; //剩余物品全部装入背包 if(n.weight >= items[n.level].weight){ boundValue = n.profit; totalWeight = n.weight; for(j=n.level+1; j<nItems; j++){ if(totalWeight+items[j].weight <= MAX_SIZE){ totalWeight += items[j].weight; boundValue += items[j].value; }else{ k = MAX_SIZE-totalWeight; boundValue += (int)(k*(items[j].value/items[j].weight)); break; } } } //剩余物品不能全部装入背包 else{ boundValue = n.profit+(int)((MAX_SIZE-n.weight)*(items[n.level].value/items[n.level].weight)); totalWeight = MAX_SIZE; } return boundValue; } //先进先出队列式分支限界法 int knapsack(int nItems, Item items[], int capacity, int *solution){ Queue q; Node u, v; int i; initQueue(&q); //初始化根结点 u.level = -1; u.profit = 0; u.weight = 0; //计算根结点的价值上界 u.bound = bound(u, nItems, items); enqueue(&q, u); int maxProfit = 0; while(!isEmpty(&q)){ u = dequeue(&q); //如果结点的价值上界小于当前最优解，则剪枝 if(u.bound <= maxProfit) continue; //扩展结点 if(u.level < nItems-1){ //不选当前物品 v.level = u.level+1; v.weight = u.weight; v.profit = u.profit; v.bound = bound(v, nItems, items); for(i=0; i<=u.level; i++){ v.select[i] = u.select[i]; } v.select[v.level] = 0; enqueue(&q, v); //选当前物品 v.level = u.level+1; v.weight = u.weight+items[v.level].weight; v.profit = u.profit+items[v.level].value; v.bound = bound(v, nItems, items); for(i=0; i<=u.level; i++){ v.select[i] = u.select[i]; } v.select[v.level] = 1; //更新当前最优解 if(v.profit > maxProfit){ maxProfit = v.profit; for(i=0; i<nItems; i++){ solution[i] = v.select[i]; } } //如果结点的价值上界大于当前最优解，则加入队列 if(v.bound > maxProfit){ enqueue(&q, v); } } } return maxProfit; } int main(){ int nItems = 5; Item items[5] = {{2, 12, 0}, {1, 10, 0}, {3, 20, 0}, {2, 15, 0}, {5, 25, 0}}; int capacity = 8; int solution[5] = {0}; int maxProfit = knapsack(nItems, items, capacity, solution); printf("Total profit: %d\n", maxProfit); printf("Solution: "); for(int i=0; i<nItems; i++){ printf("%d ", solution[i]); } printf("\n"); return 0; } ``` 其中，Item结构体存储物品的重量、价值和价值上界；Node结构体存储结点的决策树层数、当前已获得的价值、当前已占用的重量、价值上界和选择情况；Queue结构体为先进先出队列。在主函数中，定义了5个物品，背包容量为8，使用solution数组存储选中的物品，最终输出了最大价值和选择情况。