12 rizwank 1.1
13 using namespace std;
14
15 // ******************************************************************
16 // * CLASS : item *
17 // * Container object with all the data for a particular item *
18 // ******************************************************************
19 class item {
20 public:
21 float getRatio();
22 unsigned short getWeight();
23 unsigned short getCost();
24 unsigned short getNumber();
25 void setData(unsigned short,unsigned short,unsigned short);
26 private:
27 unsigned short weight;
28 unsigned short cost;
29 float ratio;
30 unsigned short number;
31 };
32
33 rizwank 1.1 // ******************************************************************
34 // * CLASS : backpack *
35 // * Container object with all the data for an entire knapsack *
36 // * Full declaration follows, partial declare here for key *
37 // ******************************************************************
38 class backpack;
39
40 // ******************************************************************
41 // * CLASS : key *
42 // * Container object with all the data for the equivalent of a node*
43 // * on the state space tree *
44 // * To allow data to remain private (and decrease the need of data *
45 // * such as max_weight and total_items to be passed along with *
46 // * every function call, a pointer to the containing backpack is *
47 // * instead implemented. *
48 // ******************************************************************
49 class key {
50 public:
51 void initKey( backpack *);
52 void flagNext();
53 void addCurItem();
54 rizwank 1.1 bool doneItems();
55 float getBound();
56 bool checkItem(unsigned short);
57 unsigned short getWeight();
58 unsigned short getValue();
59 private:
60 void calcBound();
61 bool inserted[MAX_ITEMS];
62 unsigned short nextitem;
63 unsigned short cur_weight;
64 unsigned short cur_value;
65 float upper_bound;
66 backpack *myBackpack;
67 };
68
69 // ******************************************************************
70 // * STRUCT : item_comparator *
71 // * Functor for comparing the ratio between items *
72 // ******************************************************************
73 struct item_comparator {
74 bool operator()( item left, item right ) const
75 rizwank 1.1 { return ( left.getRatio() < right.getRatio() ) ; }
76 } ;
77
78 // ******************************************************************
79 // * STRUCT : key_comparator *
80 // * Functor for comparing the bound between items *
81 // ******************************************************************
82 struct key_comparator {
83 bool operator()( key left, key right ) const
84 { return ( left.getBound() < right.getBound() ) ; }
85 } ;
86
87 // ******************************************************************
88 // * CLASS : backpack *
89 // * Container object with all the data for an entire knapsack *
90 // ******************************************************************
91 class backpack {
92 public:
93 void initBackpack(unsigned short, unsigned short);
94 void putItem(unsigned short, unsigned short);
95 void store_item_array();
96 rizwank 1.1 void branch_and_bound();
97 unsigned short get_totalItems();
98 unsigned short get_maxWeight();
99 item get_Item(unsigned short);
100 private:
101 priority_queue< item, vector<item> , item_comparator> item_queue;
102 item *item_array;
103 priority_queue< key, vector<key>, key_comparator> key_queue;
104 unsigned short totalItems;
105 unsigned short maxWeight;
106 long addnodeCount, worknodeCount;
107 };
108
109
110
111 // ******************************************************************
112 // * FUNCTION : initKey IN : CLASS key *
113 // * Initalizes a key, setting the backpack pointer and inital *
114 // * values then calculating the bound. *
115 // ******************************************************************
116 void key::initKey(backpack *theCaller){
117 rizwank 1.1 this->myBackpack = theCaller;
118 this->nextitem=0;
119 this->cur_weight=0;
120 this->cur_value=0;
121 this->calcBound();
122 }
123
124 // ******************************************************************
125 // * FUNCTION : flagNext IN : CLASS key *
126 // * Modifies the key by setting the next item as not inserted but *
127 // * as processed, then updates the bound. *
128 // ******************************************************************
129 void key::flagNext(){
130 this->inserted[this->nextitem]=0;
131 nextitem++;
132 this->calcBound();
133 }
134
135 // ******************************************************************
136 // * FUNCTION : addCurItem IN : CLASS key *
137 // * Follows up flagNext by actually marking the last item as *
138 rizwank 1.1 // * inserted, adding values and weights, then recalcing the bound. *
139 // ******************************************************************
140 void key::addCurItem(){
141 nextitem--;
142 this->inserted[this->nextitem]=1;
143 this->cur_value += (this->myBackpack->get_Item(this->nextitem)).getCost();
144 this->cur_weight += (this->myBackpack->get_Item(this->nextitem)).getWeight();
145 nextitem++;
146 this->calcBound();
147 }
148
149 // ******************************************************************
150 // * FUNCTION : doneItems IN : CLASS key *
151 // * Returns TRUE if all the items have been processed *
152 // ******************************************************************
153 bool key::doneItems(){
154 return ( this->myBackpack->get_totalItems() == this->nextitem );
155 }
156
157 // ******************************************************************
158 // * FUNCTION : getBound IN : CLASS key *
159 rizwank 1.1 // * Returns the bound. *
160 // ******************************************************************
161 float key::getBound(){
162 return this->upper_bound;
163 }
164
165 // ******************************************************************
166 // * FUNCTION : calcBound IN : CLASS key *
167 // * Calculates the bound. If there are no more items, the bound *
168 // * remains unchanged. Else, perform the calcuations. *
169 // * If the weight is over max_weight, set the bound to 0 *
170 // ******************************************************************
171 void key::calcBound(){
172 float temp;
173 if (this->doneItems()) {
174 temp = 0;
175 }
176 else {
177 temp = (float)((this->myBackpack->get_maxWeight()) - cur_weight);
178 temp = temp * (this->myBackpack->get_Item(this->nextitem)).getRatio();
179 }
180 rizwank 1.1 this->upper_bound = cur_value + temp;
181
182 // What about if the bag is overloaded?
183 if (this->cur_weight > this->myBackpack->get_maxWeight()){
184 this->upper_bound = 0; // invalidate it, will never reach 0 in bound
185 }
186 }
187
188
189 // ******************************************************************
190 // * FUNCTION : checkItem IN : CLASS key *
191 // * Checks if a given item is listed as inserted. *
192 // ******************************************************************
193 bool key::checkItem(unsigned short num) {
194 return (this->inserted[num]);
195 }
196
197 // ******************************************************************
198 // * FUNCTION : getValue IN : CLASS key *
199 // * Gets the Value of the current key. *
200 // ******************************************************************
201 rizwank 1.1 unsigned short key::getValue(){
202 return this->cur_value;
203 }
204
205 // ******************************************************************
206 // * FUNCTION : getWeight IN : CLASS key *
207 // * Gets the Weight of the current key. *
208 // ******************************************************************
209 unsigned short key::getWeight(){
210 return this->cur_weight;
211 }
212
213 // ******************************************************************
214 // * FUNCTION : getRatio IN : CLASS item *
215 // * Gets the Ratio for the current item. *
216 // ******************************************************************
217 float item::getRatio(){
218 return ratio;
219 }
220
221 // ******************************************************************
222 rizwank 1.1 // * FUNCTION : getWeight IN : CLASS item *
223 // * Gets the Weight of the current item. *
224 // ******************************************************************
225 unsigned short item::getWeight(){
226 return this->weight;
227 }
228
229 // ******************************************************************
230 // * FUNCTION : getCost IN : CLASS item *
231 // * Gets the Value of the current item. *
232 // ******************************************************************
233 unsigned short item::getCost(){
234 return this->cost;
235 }
236
237 // ******************************************************************
238 // * FUNCTION : getNumber IN : CLASS item *
239 // * Gets the Index of the current item. *
240 // ******************************************************************
241 unsigned short item::getNumber(){
242 return this->number;
243 rizwank 1.1 }
244
245 // ******************************************************************
246 // * FUNCTION : setData IN : CLASS item *
247 // * Sets all the data for an item. *
248 // ******************************************************************
249 void item::setData(unsigned short weightage, unsigned short costage, unsigned short numerage){
250 this->cost = costage;
251 this->weight = weightage;
252 this->ratio = ( (float)(cost)/(float)(weight) );
253 this->number = numerage;
254 }
255
256
257 // ******************************************************************
258 // * FUNCTION : initBackpack IN : CLASS backpack *
259 // * Initalizes the backpack values and creates the item array *
260 // ******************************************************************
261 void backpack::initBackpack(unsigned short total, unsigned short max){
262 this->totalItems = total;
263 this->maxWeight = max;
264 rizwank 1.1 item_array = new item[total];
265 worknodeCount = 0;
266 addnodeCount = 0;
267 }
268
269 // ******************************************************************
270 // * FUNCTION : putItem IN : CLASS backpack *
271 // * Creates an item and places it into the priority queue *
272 // ******************************************************************
273 void backpack::putItem(unsigned short weight, unsigned short cost){
274 item temp_item;
275 temp_item.setData(weight,cost,(int)(this->item_queue.size())+1);
276 this->item_queue.push(temp_item);
277 }
278
279 // ******************************************************************
280 // * FUNCTION : store_item_array IN : CLASS backpack *
281 // * Dumps the Item Queue in order into an Array for Rand. Access *
282 // ******************************************************************
283 void backpack::store_item_array(){
284 this->item_array = new item[this->totalItems];
285 rizwank 1.1 for ( int i = 0; this->totalItems > i; i++){
286 this->item_array[i] = this->item_queue.top();
287 this->item_queue.pop();
288 }
289 }
290
291 // ******************************************************************
292 // * FUNCTION : get_totalItems IN : CLASS backpack *
293 // * Returns the number of items for consideration. *
294 // ******************************************************************
295 unsigned short backpack::get_totalItems(){
296 return this->totalItems;
297 }
298
299 // ******************************************************************
300 // * FUNCTION : get_maxWeight IN : CLASS backpack *
301 // * Returns the maximum weight for this backpack. *
302 // ******************************************************************
303 unsigned short backpack::get_maxWeight(){
304 return this->maxWeight;
305 }
306 rizwank 1.1
307 // ******************************************************************
308 // * FUNCTION : get_Item IN : CLASS backpack *
309 // * Returns a particular item from the item array *
310 // ******************************************************************
311 item backpack::get_Item(unsigned short index){
312 return ( this->item_array[index] );
313 }
314
315 // ******************************************************************
316 // * FUNCTION : branch_and_bound IN : CLASS backpack *
317 // * Performs Best-First-Fit Branch and Bound on this backpack *
318 // * while keeping track of the nodecounts. *
319 // * Create a template key with the best possible bound. *
320 // * Place that key into the queue and start a loop *
321 // * As long as the 'onwards' flag is TRUE, repeat: *
322 // * Take the topmost (highest bound) key out of the queue. *
323 // * If that bound has all of its items processed, clear ownards *
324 // * Else, create two keys from the original key *
325 // * One without the next item and one with. *
326 // * Place the new keys into the queue and discard the current *
327 rizwank 1.1 // * Repeat *
328 // * If the loop is ended, the top item on the queue is the best *
329 // * possible solution for this knapsack. *
330 // * Fetch all the information and print it out. *
331 // ******************************************************************
332 void backpack::branch_and_bound(){
333 key temp_key;
334
335 temp_key.initKey(this);
336 this->key_queue.push(temp_key);
337 this->addnodeCount++;
338
339 bool onwards = 1;
340
341 do
342 {
343 temp_key = key_queue.top();
344 this->key_queue.pop();
345 if ( temp_key.doneItems() ) {
346 onwards = 0;
347 }
348 rizwank 1.1 else {
349 this->worknodeCount++;
350 temp_key.flagNext();
351 this->key_queue.push(temp_key);
352 this->addnodeCount++;
353 temp_key.addCurItem();
354 if (temp_key.getBound() != 0){
355 this->key_queue.push(temp_key);
356 this->addnodeCount++;
357 }
358 }
359 }
360 while (onwards);
361
362
363
364 printf("Case n=%2d Total possible nodes in thie state space tree is 2^%2d-1\n",this->totalItems,this->totalItems);
365 printf(" Number of nodes placed in the priority queue: %6d\n",this->addnodeCount);
366 printf(" Number of nodes examined/split: %6d\n",this->worknodeCount);
367
368
369 rizwank 1.1 printf("\nObjects Chosen \n");
370
371 printf(" Objects Weights Values\n");
372 int totalitemsinserted = 0;
373 for (int i = 0; this->totalItems > i; i++) {
374 if ( temp_key.checkItem(i) ) {
375 printf(" %2d %2d %2d\n", this->item_array[i].getNumber(), this->item_array[i].getWeight(), this->item_array[i].getCost());
376 totalitemsinserted++;
377 }
378 }
379 printf("======================================================\n");
380 printf("Totals: %2d %2d %2d\n",totalitemsinserted, temp_key.getWeight(), temp_key.getValue());
381 printf("Ratio : %2.5f\n", ((float)temp_key.getValue()/(float)temp_key.getWeight()));
382 }
383
384 // ******************************************************************
385 // * FUNCTION : main *
386 // * Initalizes the backpack and the items inside. *
387 // * Copies those items into an array, prints out the items. *
388 // * Run the branch_and_bound method. *
389 // ******************************************************************
390 rizwank 1.1 int main(int argc, char *argv[])
391 {
392 item temp_item;
393 printf("CS331_Project 4, by Rizwan Kassim.\n");
394 printf("Version 3\n");
395 printf("All compiled / source code are (C) Rizwan Kassim 2003\n\n");
396
397
398 printf("============================ KNAPSACK ONE ================================\n");
399 backpack knapsackOne;
400
|
402 rizwank 1.4 knapsackOne.putItem(70,70);
403 knapsackOne.putItem(76,76);
404 knapsackOne.putItem(55,55);
405 knapsackOne.putItem(17,17);
406 knapsackOne.putItem(70,70);
407 knapsackOne.putItem(77,77);
408 knapsackOne.putItem(52,52);
409 knapsackOne.putItem(81,81);
410 knapsackOne.putItem(11,11);
411 knapsackOne.putItem(31,31);
412 knapsackOne.putItem(57,57);
413 knapsackOne.putItem(47,47);
414 knapsackOne.putItem(93,93);
415 knapsackOne.putItem(53,53);
416 knapsackOne.putItem(83,83);
417 knapsackOne.putItem(33,33);
418 knapsackOne.putItem(1,1);
419 knapsackOne.putItem(59,59);
420 knapsackOne.putItem(29,29);
421 knapsackOne.putItem(33,33);
422 knapsackOne.putItem(78,78);
423 rizwank 1.4 knapsackOne.putItem(79,79);
424 knapsackOne.putItem(37,37);
425 knapsackOne.putItem(26,26);
426 knapsackOne.putItem(83,83);
|
429 rizwank 1.1 knapsackOne.store_item_array();
430
431
432 for ( int i = 0; knapsackOne.get_totalItems() > i; i++){
433 temp_item=knapsackOne.get_Item(i);
434 printf("Item Number %2d : %2d cost for %2d weight at ratio %2.3f\n", temp_item.getNumber(), temp_item.getCost(), temp_item.getWeight(), temp_item.getRatio());
435 }
436 printf("\n");
437
438 knapsackOne.branch_and_bound();
439
440 printf("\n");
441 }
442
443
444 /*
445 Modifications to the original branch-and-bound algorithim/approach
446
447 This program was to compute the maximum value that can be fit into a bag --- Using Levitin p380 for reference
448 right now. As our problem is actually a SUBSET of the given problem ,we can simplify some of the functions.
449 We also don't want any packs too small, but we'll let this compute, see how big the state tree is versus
450 rizwank 1.1 an alternative algorithm.
451
452 knapsackOne.initBackpack(5,17); // 5 total items, 17 total weight
453 knapsackOne.putItem(4,1);
454 knapsackOne.putItem(7,1);
455 knapsackOne.putItem(5,1);
456 knapsackOne.putItem(9,1);
457 knapsackOne.putItem(1,1);
458
459 For given same, 2^5-1 possible nodes in tree, 14 nodes placed, 7 split.
460
461 Lets try something larger. n=10 1,2,3,4,5,6,7,8,9,10 => 18
462
463 Oooh, we can vary the max backpack item count to only use a certain amount of the items!
464
465 Whats interesting is that we can keep the various ratio calculations, as we WOULD rather insert an item of 10 lbs rather than 1
466 We just equate weight and value later on! (Or set a fixed ratio of 1)
|
471 rizwank 1.2 And lets try with a random set of 25 numbers!
472 70,76,55,17,70,77,52,81,11,31,57,47,93,53,83,33,1,59,29,33,78,79,37,26,83 ==> 200
473
474
475
476 then 50:
477 186,130,132,108,112,39,90,88,105,172,50,46,125,79,22,192,139,132,77,195,21,129,134,76,179,89,32,55,61,160,49,191,153,86,45,16,196,109,1,178,51,104,40,88,135,100,108,182,30,48 => 1470
478
479
480
|
Return to
acm2.cpp
CVS log
Up to [RizwankCVS] / acm