2019.6.24-2019.6.28(实训数据结构) 书籍:《数据结构项目实训教程》 赵君喆,戴文华
3.4栈和队列项目实训拓展
假设有一个能装入总体积为T的背包和n件体积分别为W1,W2,……,Wn的物品,能否从n件物品中挑选出若干件恰好装满背包,
即使W1+W2+……+Wn=T,要求找出所有满足上述条件的解。例如,当T=10,各件物品的体积为{1,8,4,3,5,2}时,可找到下列4组解:
(1 ,4 ,3 ,2)、(1 ,4 ,5)、(8 ,2)、(3 ,5, 2)。
#include<iostream> #include<stdio.h> #include<algorithm> #include<stack> #include<vector> using namespace std; #define maxx 1024 int count1=0; typedef struct{ //定义顺序表结构体 int last; int data[maxx]; }seqlist; typedef struct{ //定义栈结构体 int top; int sum; int data[maxx]; }seqstack; seqstack *init_seqstack(){ //栈初始化 seqstack *s; s=new seqstack; if(!s){ printf("空间不足"); return 0; } else{ s->top=-1; s->sum=0; return s; } } int empty_seqstack(seqstack *s){ //判断空栈 if(s->top==-1) return 1; else return 0; } int push_seqstack(seqlist *l,int i,seqstack *s){ //入栈 if(s->top==maxx-1) return 0; else{ s->top++; s->data[s->top]=i; //顺序表中第i个元素,i入栈 s->sum=s->sum+l->data[i]; //栈中sum加和 return 1; } } int pop_seqstack(seqlist *l,seqstack *s,int *x){ //出栈 if(empty_seqstack(s)) return 0; else{ *x=s->data[s->top]; s->sum=s->sum-l->data[s->data[s->top]]; s->top--; return 1; } } seqlist *init_seqlist(){ seqlist *l; int x=1; l=new seqlist; l->last=0; printf("------------------------- 请依次输入物品的大小,输入0结束 "); scanf("%d",&x); while(x!=0){ l->data[l->last]=x; l->last++; scanf("%d",&x); } return l; } void knapsk(int n,seqlist *l){ //创建数组,存储物品体积 seqstack *s; int flag=1; int i=0; int t; s=init_seqstack(); //初始化栈命名为S while(flag!=0){ while(i<=l->last){ push_seqstack(l,i,s); if(s->sum==n){ printf("------------------------ 可行的解有:"); count1++; for(t=0;t<=s->top;t++){ printf("%d ",l->data[s->data[t]]); } printf(" "); pop_seqstack(l,s,&i); i++; } else{ if(s->sum>n){ pop_seqstack(l,s,&i); i++; } else{ i++; } while(i==l->last+1){ flag=pop_seqstack(l,s,&i); i++; if(flag==0){ if(count1==0) printf("无解 "); printf("------------------------- 执行完毕"); } } } } } } int main(){ int n; seqlist *l; printf("请输入背包体积n的大小,n= "); scanf("%d",&n); l=init_seqlist(); knapsk(n,l); return 1; }