//***主函数***//
void main()
{
int Len;
int Items[]={1,3,4,5,6,7}; //准备好物品
Len=6;
Knapsack knapSack;
InitKnap(knapSack); //初始化
Knapsack_Solvation(knapSack,Items,Len);
void Pop_out(Knapsack &K); //函数3----将最近放进的物品拿出来
void ShowKnap(Knapsack &K); //函数4----依次展示包中的物品
void Knapsack_Solvation(Knapsack &K,int Items[],int Len); //函数5----寻找能刚好占据包所有空间的物品组合
K.item[K.top]=item;
K.Length++;
}
void Pop_out(Knapsack &K) //函数3----将最近放进的物品拿出来
{
if(K.top==-1) //下溢
cout<<"Stack Underflow!!!"<<endl;
else
{
K.top--;
K.Length--;
Push_in(K,myitem);
temp=temp-Items[i];
if(temp==0)
ShowKnap(K); //输出所得结果
i++;
}
else //{1,3,4,5,6,7}
{
if(i=Len-1) //试探到最后一个物品
{
if(Peek(K,myitem))
{
i=myitem.item_id+1; //得到下一个物品编号
}
}
bool Peek(Knapsack &K,Myitem &myitem)
{
if(K.top==-1){
cerr<<"包中空了!"<<endl;
return false;
}
else
{
//返回栈顶元素的值
myitem=K.item[K.top];
return true;
}
}
void ShowKnap(Knapsack &K) //函数4----依次展示包中的物品
{
for(int i=0; i<K.Length; i++)
cout<<K.item[i].item_size<<" ";
cout<<endl;
}
void Knapsack_Solvation(Knapsack &K,int Items[],int Len) //函数5----寻找能刚好占据包所有空间的物品组合
数据结构用栈实现背包问题
#include<iostream>
using namespace std;
#define CAPACITY 10; //设置包的容量
//#define MaxSize 10; //包中可放物品最大数目
struct Myitem
{
int item_size;
int item_id;
//ShowKnap(knapSack);
}
//函数定义
void InitKnap(Knapsack &K) //函数1----将包清空
{
K.top=-1;
K.Length=0;
}
void Push_in(Knapsack &K,Myitem item) //函数2----将物品放入包中
{
K.top++;
{
Myitem myitem;
int temp=APACITY;
int i=0;
while(K.item[0].item_size<=7)
{
if(Items[i]<=temp) //将体积小于包当前容量的物品放入包中
{
myitem.item_size=Items[i];
myitem.item_id=i;
Pop_out(K);
temp+=Items[i-1];
}
else
break;
}
else
i++;
}
}
}
};
typedef Myitem ElemType;
struct Knapsack
{
ElemType item[10];
int Length;
int top;
};
void InitKnap(Knapsack &K); //函数1----将包清空
void Push_in(Knapsack &K,int item,int id) ; //函数2----将物品放入包中