用C语言栈实现背包问题

背包问题是一种经典的组合优化问题，其主要思想是在给定容量的背包中选择物品，使得所选物品的总价值最大。以下是使用C语言栈实现背包问题的示例代码：

#include<stdio.h>
#include<stdlib.h>

#define MAX_SIZE 100

typedef struct{
int weight; // 物品重量
int value; // 物品价值
}Item;

Item items[MAX_SIZE]; // 存储物品信息的数组
int item_count; // 物品数量
int capacity; // 背包容量
int max_value; // 最大价值
int max_weight; // 最大重量

typedef struct{
int index; // 物品编号
int weight; // 当前放入背包中的重量
int value; // 当前放入背包中的价值
}State;

State stack[MAX_SIZE]; // 栈
int top = -1; // 栈顶指针

void push(int index, int weight, int value){
top++;
stack[top].index = index;
stack[top].weight = weight;
stack[top].value = value;
}

void pop(){
top--;
}

State get_top(){
return stack[top];
}

int is_empty(){
return top == -1;
}

void dfs(int index, int weight, int value){
if(index == item_count){ // 所有物品都已考虑完
if(weight <= capacity && value > max_value){ // 能够放入背包且价值更大
max_value = value;
max_weight = weight;
}
return;
}
if(weight + items[index].weight <= capacity){ // 能够放入背包
push(index, weight, value); // 入栈
dfs(index + 1, weight + items[index].weight, value + items[index].value); // 考虑下一个物品
pop(); // 出栈
}
dfs(index + 1, weight, value); // 不放入背包，考虑下一个物品
}

int main(){
printf("请输入物品数量和背包容量：");
scanf("%d %d", &item_count, &capacity);
printf("请输入每个物品的重量和价值：\n");
for(int i = 0; i < item_count; i++){
scanf("%d %d", &items[i].weight, &items[i].value);
}
dfs(0, 0, 0); // 从第0个物品开始考虑
printf("最大价值：%d，最大重量：%d\n", max_value, max_weight);
return 0;
}