分支限界法求解0-1背包问题,规定物品数量为10，背包容量为50，输入为20个数，前十个为物品重量，后十个数为物品价值,键盘输入C语言代码

以下是使用分支限界法求解0-1背包问题的C语言代码： ```c #include<stdio.h> #include<stdlib.h> #define N 10 // 物品数量 #define C 50 // 背包容量 typedef struct { int weight; // 物品重量 int value; // 物品价值 float bound; // 松弛上界 int level; // 结点所在层数 } Node; int max_value = 0; // 最大价值 int max_weight[N+1] = {0}; // 最大价值对应的物品重量 void knapsack(int *w, int *v) { Node queue[100]; // 结点队列 int front = 0, rear = 0; // 队头和队尾指针 Node u, v1; // 初始化根结点 u.level = 0; u.weight = 0; u.value = 0; u.bound = 0; queue[rear++] = u; while (front < rear) { // 取出队头结点 u = queue[front++]; if (u.level == N) { // 叶结点 if (u.value > max_value) { max_value = u.value; for (int i = 0; i < N; i++) { max_weight[i] = 0; } for (int i = N-1; i >= 0; i--) { if (u.weight >= w[i]) { max_weight[i] = 1; u.weight -= w[i]; } else { max_weight[i] = u.weight / w[i]; break; } } } continue; } // 计算左儿子结点的松弛上界 v1.level = u.level + 1; v1.weight = u.weight + w[v1.level - 1]; v1.value = u.value + v[v1.level - 1]; if (v1.weight <= C) { v1.bound = v1.value; for (int i = v1.level; i < N; i++) { if (v1.weight + w[i] <= C) { v1.weight += w[i]; v1.value += v[i]; } else { v1.bound += (C - v1.weight) * 1.0 / w[i] * v[i]; break; } } if (v1.bound > max_value) { // 产生新结点 queue[rear++] = v1; } } // 计算右儿子结点的松弛上界 v1.level = u.level + 1; v1.weight = u.weight; v1.value = u.value; v1.bound = v1.value; for (int i = v1.level; i < N; i++) { if (v1.weight + w[i] <= C) { v1.weight += w[i]; v1.value += v[i]; } else { v1.bound += (C - v1.weight) * 1.0 / w[i] * v[i]; break; } } if (v1.bound > max_value) { // 产生新结点 queue[rear++] = v1; } } } int main() { int w[N], v[N]; printf("请输入%d个数，前%d个为物品重量，后%d个为物品价值：\n", N*2, N, N); for (int i = 0; i < N; i++) { scanf("%d", &w[i]); } for (int i = 0; i < N; i++) { scanf("%d", &v[i]); } knapsack(w, v); printf("最大价值：%d\n", max_value); printf("选择的物品重量为："); for (int i = 0; i < N; i++) { printf("%d ", max_weight[i] * w[i]); } printf("\n"); return 0; } ```