90 lines
3.6 KiB
C
90 lines
3.6 KiB
C
|
#include <stdio.h>
|
|||
|
|
#include <stdbool.h>
|
|||
|
|
#define CAPACITY 30
|
|||
|
|
#define N 3
|
|||
|
|
#define QUEUE_SIZE 100 // 定义队列的最大容量（静态分配）
|
|||
|
|
typedef struct {// 定义节点结构体
|
|||
|
|
int level; // 当前节点所在的层数（即考虑第几个物品）
|
|||
|
|
int weight; // 当前已装入物品的总重量
|
|||
|
|
int value; // 当前已获得的总价值
|
|||
|
|
bool items[N]; // 布尔数组，记录每个物品是否被选择
|
|||
|
|
} Node;
|
|||
|
|
// 定义队列结构体，使用数组模拟队列
|
|||
|
|
typedef struct {
|
|||
|
|
Node liveList[QUEUE_SIZE]; // 队列的存储数组
|
|||
|
|
int front, rear; // 队列的头部和尾部指针
|
|||
|
|
} Queue;
|
|||
|
|
// 初始化队列，设置front为0，rear为-1表示空队列
|
|||
|
|
void initQueue(Queue* queue) {
|
|||
|
|
queue->front = 0; queue->rear = -1;
|
|||
|
|
}
|
|||
|
|
// 检查队列是否为空，如果front大于rear则为空
|
|||
|
|
int isEmpty(Queue* queue) {
|
|||
|
|
return queue->front > queue->rear;
|
|||
|
|
}
|
|||
|
|
// 向队列中添加元素，使用前置自增保证新元素放置在正确位置
|
|||
|
|
void insertQueue(Queue* queue, Node item) {
|
|||
|
|
queue->liveList[++(queue->rear)] = item;
|
|||
|
|
}
|
|||
|
|
// 从队列中移除并返回元素，如果队列为空则返回一个空节点
|
|||
|
|
Node popQueue(Queue* queue) {
|
|||
|
|
if (isEmpty(queue)) {
|
|||
|
|
static Node emptyNode = {-1, -1, -1, {false}};
|
|||
|
|
return emptyNode;
|
|||
|
|
}
|
|||
|
|
return queue->liveList[(queue->front)++];
|
|||
|
|
}
|
|||
|
|
// 使用广度优先搜索（BFS）解决01背包问题
|
|||
|
|
void bag01bfs(Queue* queue, int weightArr[], int value[], int n, int maxWeight,
|
|||
|
|
int* maxValue, bool bestItems[]) {
|
|||
|
|
// 创建初始节点（level=0，weight=0，value=0，items全为false），并将其加入队列
|
|||
|
|
Node node = {0, 0, 0, {false}};
|
|||
|
|
insertQueue(queue, node);
|
|||
|
|
while (!isEmpty(queue)) { // 开始广度优先搜索
|
|||
|
|
Node u = popQueue(queue); // 取出队列中的第一个节点
|
|||
|
|
// 如果遇到空节点，跳过本次循环
|
|||
|
|
if (u.level == -1) continue;
|
|||
|
|
if (u.level == n) { // 如果到达最后一层（所有物品都考虑完毕）
|
|||
|
|
if (u.value > *maxValue) { // 更新最大价值和最优解
|
|||
|
|
*maxValue = u.value;
|
|||
|
|
for (int i = 0; i < N; ++i)
|
|||
|
|
bestItems[i] = u.items[i];
|
|||
|
|
}
|
|||
|
|
continue;
|
|||
|
|
}
|
|||
|
|
// 分支：包含当前物品的情况
|
|||
|
|
if (u.weight + weightArr[u.level] <= maxWeight) {
|
|||
|
|
// 创建新节点v，代表选择了当前物品的情况
|
|||
|
|
Node v = {u.level + 1, u.weight + weightArr[u.level], u.value + value[u.level]};
|
|||
|
|
for (int i = 0; i < N; ++i)
|
|||
|
|
v.items[i] = u.items[i];
|
|||
|
|
v.items[u.level] = true;
|
|||
|
|
insertQueue(queue, v);
|
|||
|
|
}
|
|||
|
|
// 分支：不包含当前物品的情况
|
|||
|
|
Node w = {u.level + 1, u.weight, u.value};
|
|||
|
|
for (int i = 0; i < N; ++i)
|
|||
|
|
w.items[i] = u.items[i];
|
|||
|
|
insertQueue(queue, w);
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
int main() {
|
|||
|
|
// 定义每个物品的重量和价值
|
|||
|
|
int weightArr[N] = {16, 15, 15}; // 每个物品的重量
|
|||
|
|
int value[N] = {45, 25, 25}; // 每个物品的价值
|
|||
|
|
int maxValue = 0; // 最大价值
|
|||
|
|
bool bestItems[N] = {false}; // 记录最优解的物品选择情况
|
|||
|
|
Queue queue;
|
|||
|
|
initQueue(&queue); // 初始化队列
|
|||
|
|
// 调用bag01bfs函数解决背包问题
|
|||
|
|
bag01bfs(&queue, weightArr, value, N, CAPACITY, &maxValue, bestItems);
|
|||
|
|
// 输出结果
|
|||
|
|
printf("最大价值是 %d\n", maxValue);
|
|||
|
|
printf("选择的物品：");
|
|||
|
|
for (int i = 0; i < N; ++i) {
|
|||
|
|
if (bestItems[i])
|
|||
|
|
printf("%d ", i + 1); // 输出物品编号（从1开始）
|
|||
|
|
}
|
|||
|
|
return 0;
|
|||
|
|
}
|