1//说明：本程序有一定代码冗余，若分割为多个函数的形式会使程序简洁明了。
2#include <iostream>
3using namespace std;
4#include <queue>
5#include <stack>
6
7const int N=5; //物品个数，其中包括（0,0）.
8const float W=60; //背包最大载重。
9struct GoodsStruct
10{
11 int ID; //物品编号
12 float benefit; //物品效益
13 float weight; //物品重量
14 int com; //标记最优解中是否含有该物品，有则为1,没有则为0.
15};
16
17int main()
18{
19 GoodsStruct StructGoods;
20 GoodsStruct StructTemp;
21 GoodsStruct StructCom;
22 GoodsStruct StructCalTemp;
23 queue <GoodsStruct> QueueGoods; //存放原始物品信息的队列，用于求解集合，完后全部被弹出。
24 queue <GoodsStruct> QueueSourse;//存放原始物品信息的队列，用于回溯过程，作为最后结果。
25 queue <GoodsStruct> QueueTemp;
26 queue <GoodsStruct> QueuePush;
27 queue <GoodsStruct> QueueCom; //两个队列在支配规则下的合并结果队列。
28 queue <GoodsStruct> QueueComTemp;//两个队列在支配规则下的合并时的临时变量。
29 queue <GoodsStruct> QueueCalTemp;
30 stack <queue<GoodsStruct>> StackGoods;
31
32 /**//*float benefits[N]={0,2,2,1};//测试数据。
33 float weights[N]={0,2,3,2};*/
34 /**//*float benefits[N]={0,2,3,4};
35 float weights[N]={0,1,2,5};*/
36 float benefits[N]={0,2,5,8,1};
37 float weights[N]={0,10,15,6,9};
38 bool check=false;
39
40 //将物品信息存入队列和堆栈中。
41 for (int i=0;i<N;i++)
42 {
43 StructTemp.ID=i;
44 StructTemp.benefit=benefits[i];
45 StructTemp.weight=weights[i];
46 StructTemp.com=0;
47 QueueSourse.push(StructTemp);
48 }
49
50 /**///
51 //求解集合
52 //(0,0)先入栈。
53 QueueGoods=QueueSourse;
54 StructGoods=QueueGoods.front();
55 QueueGoods.pop();
56 QueuePush.push(StructGoods);
57 StackGoods.push(QueuePush);
58
59 while (!QueueGoods.empty())
60 {
61 StructGoods=QueueGoods.front();
62 QueueGoods.pop();
63 QueueTemp=QueuePush;
64 //计算出临时队列的过程，此处使用支配规则。
65 while (!QueueTemp.empty())
66 {
67 StructTemp=QueueTemp.front();
68 QueueTemp.pop();
69 StructTemp.benefit+=StructGoods.benefit;
70 StructTemp.weight+=StructGoods.weight;
71
72 QueueCalTemp=QueuePush;
73 if (StructTemp.weight<=W)
74 {
75 while (!QueueCalTemp.empty())
76 {
77 StructCalTemp=QueueCalTemp.front();
78 QueueCalTemp.pop();
79 if (StructTemp.weight>=StructCalTemp.weight && StructTemp.benefit<StructCalTemp.benefit)
80 {
81 //支配规则把新值StructCom去掉。
82 check=false;
83 break;
84 }
85 else
86 {
87 check=true;
88 }
89 }
90 if (check==true)
91 {
92 QueueComTemp.push(StructTemp);
93 }
94 }
95 }
96
97 //QueueComTemp与QueuePush通过支配规则进行合并，去掉不可能的解。
98 while (!QueuePush.empty())
99 {
100 StructCom=QueuePush.front();
101 QueuePush.pop();
102 QueueTemp=QueueComTemp;
103 while (!QueueTemp.empty())
104 {
105 StructTemp=QueueTemp.front();
106 QueueTemp.pop();
107 if (StructCom.weight>=StructTemp.weight && StructCom.benefit<StructTemp.benefit)
108 {
109 //支配规则把新值StructCom去掉。
110 check=false;
111 break;
112 }
113 else
114 {
115 check=true;
116 }
117 }
118 if (check==true)
119 {
120 QueueCom.push(StructCom);
121 }
122 }
123 //将QueueComTemp全部接入QueueCom中，因为QueueComTemp不会被支配掉。
124 while (!QueueComTemp.empty())
125 {
126 StructTemp=QueueComTemp.front();
127 QueueComTemp.pop();
128 QueueCom.push(StructTemp);
129 }
130 StackGoods.push(QueueCom);
131 QueuePush=QueueCom;
132 while (!QueueCom.empty())
133 {
134 QueueCom.pop();
135 }
136 }
137
138 /**///
139 //求解最终序偶
140 QueueTemp=StackGoods.top();
141 StructGoods=QueueTemp.back();
142 while (!QueueTemp.empty())
143 {
144 StructTemp=QueueTemp.front();
145 QueueTemp.pop();
146 if (StructGoods.weight<StructTemp.weight)
147 {
148 StructGoods=StructTemp;
149 }
150 }
151 cout<<"(P,W)=("<<StructGoods.benefit<<","<<StructGoods.weight<<")"<<endl;
152
153 /**///
154 //回溯
155 int count=N-1;
156 StackGoods.pop();
157 while(!StackGoods.empty())
158 {
159 QueueTemp=StackGoods.top();
160 StackGoods.pop();
161 while (!QueueTemp.empty())
162 {
163 StructTemp=QueueTemp.front();
164 QueueTemp.pop();
165 if (StructTemp.benefit==StructGoods.benefit && StructTemp.weight==StructGoods.weight)
166 {
167 check=false;
168 for (int i=0;i<N;i++)
169 {
170 StructCalTemp=QueueSourse.front();
171 QueueSourse.pop();
172 if (StructCalTemp.ID==count)
173 {
174 StructCalTemp.com=0;
175 }
176 QueueSourse.push(StructCalTemp);
177 }
178 break;
179 }
180 else
181 {
182 check=true;
183 }
184 }
185 if (check==true)
186 {
187 for (int i=0;i<N;i++)
188 {
189 StructCalTemp=QueueSourse.front();
190 QueueSourse.pop();
191 if (StructCalTemp.ID==count)
192 {
193 StructCalTemp.com=1;
194 }
195 QueueSourse.push(StructCalTemp);
196 }
197 StructGoods.benefit-=StructCalTemp.benefit;
198 StructGoods.weight-=StructCalTemp.weight;
199 }
200 count--;
201 }
202
203 QueueSourse.pop();
204 while(!QueueSourse.empty())
205 {
206 StructTemp=QueueSourse.front();
207 QueueSourse.pop();
208 cout<<"X"<<count+1<<"="<<StructTemp.com<<endl;
209 count++;
210 }
211 return 0;
212}
转载于:https://www.cnblogs.com/fireice/archive/2009/05/02/1447928.html