1 rizwank 1.11 #include<stdlib.h>
2 #include<iostream>
3 #include<fstream>
4 #include<string>
|
5 rizwank 1.1 #include <queue>
|
6 rizwank 1.12 #include <stack>
|
7 rizwank 1.13 #include <vector>
|
8 rizwank 1.1 #include <stdio.h>
|
9 rizwank 1.11 // yes I could use just one i/o lib
10 using namespace std;
11
|
12 rizwank 1.1
13 // As per specification, the project has to be able to grow to an
14 // arbitrary amount of items. MAX_ITEMS describes the size of the
15 // appropriate arrays and must be changed at compile time.
16 // (dynamically created arrays had their pointers corrupted when
17 // their parent object was in the priority queue, so static sized
18 // arrays were used
19
|
20 rizwank 1.12 #define MAX_ITEMS 65536
21 //the above bound comes from the fixed value for the boolean array TODO REMOVE LIMITATION
|
22 rizwank 1.1
|
23 rizwank 1.14 #define EARLYSKIP
24
|
25 rizwank 1.11 typedef long ITEM_MASS;
|
26 rizwank 1.9 typedef long INDEX_TYPE;
27
28
|
29 rizwank 1.1 using namespace std;
30
31 // ******************************************************************
32 // * CLASS : item *
33 // * Container object with all the data for a particular item *
34 // ******************************************************************
35 class item {
36 public:
|
37 rizwank 1.8 // float getRatio();
|
38 rizwank 1.9 ITEM_MASS getWeight();
39 // ITEM_MASS getNumber();
|
40 rizwank 1.10 void setData(ITEM_MASS);
|
41 rizwank 1.1 private:
|
42 rizwank 1.9 ITEM_MASS weight;
|
43 rizwank 1.8 // float ratio;
|
44 rizwank 1.9 // ITEM_MASS number;
|
45 rizwank 1.1 };
46
47 // ******************************************************************
48 // * CLASS : backpack *
49 // * Container object with all the data for an entire knapsack *
50 // * Full declaration follows, partial declare here for key *
51 // ******************************************************************
52 class backpack;
53
54 // ******************************************************************
55 // * CLASS : key *
56 // * Container object with all the data for the equivalent of a node*
57 // * on the state space tree *
58 // * To allow data to remain private (and decrease the need of data *
59 // * such as max_weight and total_items to be passed along with *
60 // * every function call, a pointer to the containing backpack is *
61 // * instead implemented. *
62 // ******************************************************************
63 class key {
64 public:
65 void initKey( backpack *);
66 rizwank 1.1 void flagNext();
67 void addCurItem();
68 bool doneItems();
69 float getBound();
|
70 rizwank 1.9 bool checkItem(INDEX_TYPE);
71 ITEM_MASS getWeight();
|
72 rizwank 1.14 void makeDone();
|
73 rizwank 1.1 private:
74 void calcBound();
75 bool inserted[MAX_ITEMS];
|
76 rizwank 1.9 INDEX_TYPE nextitem;
77 ITEM_MASS cur_weight;
|
78 rizwank 1.1 float upper_bound;
79 backpack *myBackpack;
80 };
81
82 // ******************************************************************
83 // * STRUCT : item_comparator *
84 // * Functor for comparing the ratio between items *
85 // ******************************************************************
86 struct item_comparator {
87 bool operator()( item left, item right ) const
|
88 rizwank 1.8 // { return ( left.getRatio() < right.getRatio() ) ; }
89 { return 0 ; } //same ratio to all, don't actually do a compare!
|
90 rizwank 1.1 } ;
91
92 // ******************************************************************
93 // * STRUCT : key_comparator *
94 // * Functor for comparing the bound between items *
95 // ******************************************************************
96 struct key_comparator {
97 bool operator()( key left, key right ) const
98 { return ( left.getBound() < right.getBound() ) ; }
99 } ;
100
101 // ******************************************************************
102 // * CLASS : backpack *
103 // * Container object with all the data for an entire knapsack *
104 // ******************************************************************
105 class backpack {
106 public:
|
107 rizwank 1.9 void initBackpack(INDEX_TYPE, ITEM_MASS);
|
108 rizwank 1.10 void putItem(ITEM_MASS);//, ITEM_MASS);
|
109 rizwank 1.1 void store_item_array();
|
110 rizwank 1.11 void branch_and_bound(int,ITEM_MASS);
|
111 rizwank 1.9 ITEM_MASS get_totalItems();
112 ITEM_MASS get_maxWeight();
113 item get_Item(INDEX_TYPE);
|
114 rizwank 1.1 private:
115 priority_queue< item, vector<item> , item_comparator> item_queue;
116 item *item_array;
117 priority_queue< key, vector<key>, key_comparator> key_queue;
|
118 rizwank 1.9 INDEX_TYPE totalItems;
119 ITEM_MASS maxWeight;
|
120 rizwank 1.1 long addnodeCount, worknodeCount;
121 };
122
123
124
125 // ******************************************************************
126 // * FUNCTION : initKey IN : CLASS key *
127 // * Initalizes a key, setting the backpack pointer and inital *
128 // * values then calculating the bound. *
129 // ******************************************************************
130 void key::initKey(backpack *theCaller){
131 this->myBackpack = theCaller;
132 this->nextitem=0;
133 this->cur_weight=0;
134 this->calcBound();
|
135 rizwank 1.14 for ( int i = 0; MAX_ITEMS > i; i++) {
136 this->inserted[i] = 0;
137 }
|
138 rizwank 1.1 }
139
140 // ******************************************************************
141 // * FUNCTION : flagNext IN : CLASS key *
142 // * Modifies the key by setting the next item as not inserted but *
143 // * as processed, then updates the bound. *
144 // ******************************************************************
145 void key::flagNext(){
|
146 rizwank 1.14 this->inserted[this->nextitem]= 0;
|
147 rizwank 1.1 nextitem++;
148 this->calcBound();
149 }
150
151 // ******************************************************************
152 // * FUNCTION : addCurItem IN : CLASS key *
153 // * Follows up flagNext by actually marking the last item as *
154 // * inserted, adding values and weights, then recalcing the bound. *
155 // ******************************************************************
156 void key::addCurItem(){
157 nextitem--;
158 this->inserted[this->nextitem]=1;
159 this->cur_weight += (this->myBackpack->get_Item(this->nextitem)).getWeight();
160 nextitem++;
161 this->calcBound();
162 }
163
164 // ******************************************************************
165 // * FUNCTION : doneItems IN : CLASS key *
166 // * Returns TRUE if all the items have been processed *
167 // ******************************************************************
168 rizwank 1.1 bool key::doneItems(){
169 return ( this->myBackpack->get_totalItems() == this->nextitem );
170 }
171
|
172 rizwank 1.14 void key::makeDone(){
173 this->nextitem = this->myBackpack->get_totalItems();
174 }
175
|
176 rizwank 1.1 // ******************************************************************
177 // * FUNCTION : getBound IN : CLASS key *
178 // * Returns the bound. *
179 // ******************************************************************
180 float key::getBound(){
181 return this->upper_bound;
182 }
183
184 // ******************************************************************
185 // * FUNCTION : calcBound IN : CLASS key *
186 // * Calculates the bound. If there are no more items, the bound *
187 // * remains unchanged. Else, perform the calcuations. *
188 // * If the weight is over max_weight, set the bound to 0 *
189 // ******************************************************************
190 void key::calcBound(){
|
191 rizwank 1.14 ITEM_MASS temp;
|
192 rizwank 1.1 if (this->doneItems()) {
193 temp = 0;
194 }
195 else {
|
196 rizwank 1.14 temp = ((this->myBackpack->get_maxWeight()) - cur_weight);
|
197 rizwank 1.7 // temp = temp * (this->myBackpack->get_Item(this->nextitem)).getRatio(); (ratio = 1!)
|
198 rizwank 1.1 }
|
199 rizwank 1.14 this->upper_bound = cur_weight + temp;
|
200 rizwank 1.1
201 // What about if the bag is overloaded?
|
202 rizwank 1.14 if (this->cur_weight > this->myBackpack->get_maxWeight() ){
|
203 rizwank 1.1 this->upper_bound = 0; // invalidate it, will never reach 0 in bound
204 }
205 }
206
207
208 // ******************************************************************
209 // * FUNCTION : checkItem IN : CLASS key *
210 // * Checks if a given item is listed as inserted. *
211 // ******************************************************************
|
212 rizwank 1.9 bool key::checkItem(INDEX_TYPE num) {
|
213 rizwank 1.1 return (this->inserted[num]);
214 }
215
216 // ******************************************************************
217 // * FUNCTION : getValue IN : CLASS key *
218 // * Gets the Value of the current key. *
219 // ******************************************************************
|
220 rizwank 1.14 //ITEM_MASS key::getValue(){
221 // return this->cur_value;
222 //}
|
223 rizwank 1.1
224 // ******************************************************************
225 // * FUNCTION : getWeight IN : CLASS key *
226 // * Gets the Weight of the current key. *
227 // ******************************************************************
|
228 rizwank 1.9 ITEM_MASS key::getWeight(){
|
229 rizwank 1.1 return this->cur_weight;
230 }
231
232 // ******************************************************************
233 // * FUNCTION : getRatio IN : CLASS item *
234 // * Gets the Ratio for the current item. *
235 // ******************************************************************
|
236 rizwank 1.8 //float item::getRatio(){
237 // return ratio;
238 //}
|
239 rizwank 1.1
240 // ******************************************************************
241 // * FUNCTION : getWeight IN : CLASS item *
242 // * Gets the Weight of the current item. *
243 // ******************************************************************
|
244 rizwank 1.9 ITEM_MASS item::getWeight(){
|
245 rizwank 1.1 return this->weight;
246 }
247
248 // ******************************************************************
249 // * FUNCTION : getCost IN : CLASS item *
250 // * Gets the Value of the current item. *
251 // ******************************************************************
|
252 rizwank 1.14 ///ITEM_MASS item::getCost(){
253 /// return this->cost;
254 ///}
|
255 rizwank 1.1
256 // ******************************************************************
257 // * FUNCTION : getNumber IN : CLASS item *
258 // * Gets the Index of the current item. *
259 // ******************************************************************
|
260 rizwank 1.9 //ITEM_MASS item::getNumber(){
261 // return this->number;
262 //}
|
263 rizwank 1.1
264 // ******************************************************************
265 // * FUNCTION : setData IN : CLASS item *
266 // * Sets all the data for an item. *
267 // ******************************************************************
|
268 rizwank 1.10 void item::setData(ITEM_MASS weightage){ //, ITEM_MASS costage, ITEM_MASS numerage){
|
269 rizwank 1.14 // this->cost = weightage; //costage;
|
270 rizwank 1.1 this->weight = weightage;
|
271 rizwank 1.7 // this->ratio = ( (float)(cost)/(float)(weight) );
|
272 rizwank 1.8 // this->ratio = 1; //ratio = 1
|
273 rizwank 1.9 // this->number = numerage;
|
274 rizwank 1.1 }
275
276
277 // ******************************************************************
278 // * FUNCTION : initBackpack IN : CLASS backpack *
279 // * Initalizes the backpack values and creates the item array *
280 // ******************************************************************
|
281 rizwank 1.9 void backpack::initBackpack(INDEX_TYPE total, ITEM_MASS max){
|
282 rizwank 1.1 this->totalItems = total;
283 this->maxWeight = max;
284 item_array = new item[total];
285 worknodeCount = 0;
286 addnodeCount = 0;
287 }
288
289 // ******************************************************************
290 // * FUNCTION : putItem IN : CLASS backpack *
291 // * Creates an item and places it into the priority queue *
292 // ******************************************************************
|
293 rizwank 1.10 void backpack::putItem(ITEM_MASS weight){ //, ITEM_MASS cost){
|
294 rizwank 1.1 item temp_item;
|
295 rizwank 1.10 temp_item.setData(weight);//,cost);//,(int)(this->item_queue.size())+1); // sometimes this starts at 2000?
|
296 rizwank 1.1 this->item_queue.push(temp_item);
297 }
298
299 // ******************************************************************
300 // * FUNCTION : store_item_array IN : CLASS backpack *
301 // * Dumps the Item Queue in order into an Array for Rand. Access *
302 // ******************************************************************
303 void backpack::store_item_array(){
304 this->item_array = new item[this->totalItems];
305 for ( int i = 0; this->totalItems > i; i++){
306 this->item_array[i] = this->item_queue.top();
307 this->item_queue.pop();
308 }
309 }
310
311 // ******************************************************************
312 // * FUNCTION : get_totalItems IN : CLASS backpack *
313 // * Returns the number of items for consideration. *
314 // ******************************************************************
|
315 rizwank 1.9 ITEM_MASS backpack::get_totalItems(){
|
316 rizwank 1.1 return this->totalItems;
317 }
318
319 // ******************************************************************
320 // * FUNCTION : get_maxWeight IN : CLASS backpack *
321 // * Returns the maximum weight for this backpack. *
322 // ******************************************************************
|
323 rizwank 1.9 ITEM_MASS backpack::get_maxWeight(){
|
324 rizwank 1.1 return this->maxWeight;
325 }
326
327 // ******************************************************************
328 // * FUNCTION : get_Item IN : CLASS backpack *
329 // * Returns a particular item from the item array *
330 // ******************************************************************
|
331 rizwank 1.9 item backpack::get_Item(INDEX_TYPE index){
|
332 rizwank 1.1 return ( this->item_array[index] );
333 }
334
335 // ******************************************************************
336 // * FUNCTION : branch_and_bound IN : CLASS backpack *
337 // * Performs Best-First-Fit Branch and Bound on this backpack *
338 // * while keeping track of the nodecounts. *
339 // * Create a template key with the best possible bound. *
340 // * Place that key into the queue and start a loop *
341 // * As long as the 'onwards' flag is TRUE, repeat: *
342 // * Take the topmost (highest bound) key out of the queue. *
343 // * If that bound has all of its items processed, clear ownards *
344 // * Else, create two keys from the original key *
345 // * One without the next item and one with. *
346 // * Place the new keys into the queue and discard the current *
347 // * Repeat *
348 // * If the loop is ended, the top item on the queue is the best *
349 // * possible solution for this knapsack. *
350 // * Fetch all the information and print it out. *
351 // ******************************************************************
|
352 rizwank 1.11 void backpack::branch_and_bound(int DEBUG_MODE, ITEM_MASS targetvalue){
|
353 rizwank 1.1 key temp_key;
354
355 temp_key.initKey(this);
356 this->key_queue.push(temp_key);
357 this->addnodeCount++;
358
359 bool onwards = 1;
360 do
361 {
362 temp_key = key_queue.top();
363 this->key_queue.pop();
|
364 rizwank 1.14 /*Early skip here -- MASSIVE speed improvements */
365 if ( temp_key.getWeight() == targetvalue ) {
366 printf("Early value acquired! %d\n",temp_key.getWeight() );
367 goto early; // yes thats a go to. Its the only way to leave and keep the context right. I know its horrible
368 }
|
369 rizwank 1.1 if ( temp_key.doneItems() ) {
370 onwards = 0;
371 }
372 else {
373 this->worknodeCount++;
374 temp_key.flagNext();
375 this->key_queue.push(temp_key);
376 this->addnodeCount++;
|
377 rizwank 1.14
378
379 // try this --- compare quicksorted before and after because of greedy grabbing largest
380 //should find other comparator for weight with sub data like ... pct done
381
382
383
384
|
385 rizwank 1.1 temp_key.addCurItem();
386 if (temp_key.getBound() != 0){
387 this->key_queue.push(temp_key);
388 this->addnodeCount++;
389 }
390 }
|
391 rizwank 1.14 // if ((this->addnodeCount % 1000) == 0) {printf("10000!");}
|
392 rizwank 1.1 }
393 while (onwards);
394
|
395 rizwank 1.14 early: if (DEBUG_MODE) {
|
396 rizwank 1.11 printf("Case n=%2d Total possible nodes in thie state space tree is 2^%2d-1\n",this->totalItems,this->totalItems);
397 printf(" Number of nodes placed in the priority queue: %6d\n",this->addnodeCount);
398 printf(" Number of nodes examined/split: %6d\n",this->worknodeCount);
399 /* printf("\nObjects Chosen \n");
400
401 printf("\t\tWeights\tValues\n");
402 int totalitemsinserted = 0;
403 for (int i = 0; this->totalItems > i; i++) {
404 if ( temp_key.checkItem(i) ) {
405 printf("\t\t%4.2f\t%4.2f\n", this->item_array[i].getWeight(), this->item_array[i].getCost());
406 totalitemsinserted++; // this->item_array[i].getNumber(), removed
407 }
408 }
409 printf("======================================================\n");
410 printf("Totals:\t%3d\t%4.2f\t%4.2f\n",totalitemsinserted, temp_key.getWeight(), temp_key.getValue());
411 // printf("Ratio : %2.5f\n", ((float)temp_key.getValue()/(float)temp_key.getWeight())); */
412 }
413
414
|
415 rizwank 1.12 if ( temp_key.getWeight() == targetvalue ) {
|
416 rizwank 1.11 int totalitemsinserted = 0;
417 int first=1;
418 for (int i = 0; this->totalItems > i; i++) {
419 if ( temp_key.checkItem(i) ) {
420 if (first==0) { printf(","); }
421 else {first = 0;} // there has GOT to be a better way!
422 printf("%d", this->item_array[i].getWeight());
423 }
424 }
|
425 rizwank 1.12 }
426 else { printf("CANNOT FILL PALLET\n"); }
|
427 rizwank 1.11 }
|
428 rizwank 1.1
|
429 rizwank 1.11 // have to deal with non int #s
|
430 rizwank 1.13
431 void super_increase_algo ( vector<ITEM_MASS> inventory, ITEM_MASS target_value , INDEX_TYPE size_inventory, int DEBUG_MODE ) {
432 stack<ITEM_MASS> packages_to_load;
|
433 rizwank 1.1
|
434 rizwank 1.13 if (DEBUG_MODE) {
435 printf("Extracting values, highest to lowest, doing reduction from index %d\n",size_inventory);
436 }
437 for ( INDEX_TYPE store_index=size_inventory-1; store_index>=0;store_index-- ) {
438 if (DEBUG_MODE) {
439 printf("value %d, is it smaller than %d? If so, subtract and store.\n",inventory[store_index],target_value);
440 }
441 if ( inventory[store_index] <= target_value ) {
442 target_value = target_value - inventory[store_index];
443 packages_to_load.push(inventory[store_index]);
444 }
445 }
446 if ( target_value == 0 ) {
447 int first = 1;
448 while ( ! packages_to_load.empty() ) {
449 if (first==0) { printf(","); }
450 else {first = 0;} // there has GOT to be a better way!
451 printf("%d",packages_to_load.top());
452 packages_to_load.pop();
453 }
454 printf("\n");
455 rizwank 1.13 }
456 else { printf("CANNOT FILL PALLET\n"); }
457 }
458
459
|
460 rizwank 1.11 void syntaxmsg(){
461 printf("Usage:\n");
462 printf("<program name> <input filename> <D/d>\n");
463 printf("input contains a series of integers [A], comma delimited,\n\t followed by a CR and an int [B]\n");
464 printf("program outputs a comma delimited list of elements of A that sum to B,\n\t or CANNOT FILL PALLET\n");
465 printf("Program written for the UCLA ACM Feb 2005 Coding Competition\n");
466 printf("Dervied from previous academic work written by the author\n(C) 2002-2005 Rizwan Kassim\n");
467 printf("If the second argument is a D or d, verbose debugging mode will be enabled\n\n");
468 return;
|
469 rizwank 1.1 }
470
|
471 rizwank 1.14
472 ITEM_MASS masscomp (const void * a, const void * b)
473 {
474 return ( *(ITEM_MASS*)a - *(ITEM_MASS*)b );
475 }
476
477
|
478 rizwank 1.1 // ******************************************************************
479 // * FUNCTION : main *
480 // * Initalizes the backpack and the items inside. *
481 // * Copies those items into an array, prints out the items. *
482 // * Run the branch_and_bound method. *
483 // ******************************************************************
484 int main(int argc, char *argv[])
485 {
486 item temp_item;
|
487 rizwank 1.11 int DEBUG_MODE = 0;
|
488 rizwank 1.1
|
489 rizwank 1.11 if ( argc < 2 ) { syntaxmsg(); return 2;}
490 if ( argc > 4 ) { syntaxmsg(); return 3;}
491 if ( argc == 3 ) {
492 if ( argv[2][0] == 'D' || argv[2][0] == 'd' ) {
493 printf("Debug switch caught, outputing debug messages\n");
494 DEBUG_MODE =1;
495 } else { syntaxmsg(); return 4;}
496 }
497
498 if (DEBUG_MODE) {
499 printf("Entry into UCLA ACM Feb. 2005 Coding Competition\n");
500 printf("Based on code developed (myself) for CS331 Project 4 at CSU Pomona\n");
501 printf("Version 4\n");
502 printf("All compiled / source code are (C) Rizwan Kassim 2005\n\n");
503 }
504
505
506 INDEX_TYPE max_inventory;
507
508 ifstream inputfs;
509 inputfs.open (argv[1]);
510 rizwank 1.11 if (!inputfs.is_open())
511 { printf("File open of %s failed!\n", argv[1]);
512 syntaxmsg();
513 return 1; }
514 if (DEBUG_MODE) {
515 printf("File %s Open!\n",argv[1]);
516 }
517
518 INDEX_TYPE length;
519 inputfs.seekg (0, ios::end);
520 length = inputfs.tellg();
521 inputfs.seekg (0, ios::beg);
522
523 char * read_buffer = (char *) malloc (length);
|
524 rizwank 1.13 vector<ITEM_MASS> inventory;
|
525 rizwank 1.12 // could use stack instead of array --- doesn't require malloc, more 'safe' avoids overflows, esp if
526 // input file is funky --- its better software engineering, but its slower. Given that this is a pretty
|
527 rizwank 1.13 // small system, I'll stick with the array --- oh even better -- a vector!
|
528 rizwank 1.14 //http://theory.stanford.edu/~amitp/rants/c++-vs-c/ Vector speed sorting is optimized by using vector!
|
529 rizwank 1.11 inputfs.getline (read_buffer, length-1);
530
531 char * theToken; INDEX_TYPE index = 0;
532 theToken=strtok(read_buffer,",");
533 // assume 1+ items
534 while ( theToken != NULL ) {
535 //printf("tokendebug %d %f\n",theToken,theToken);
|
536 rizwank 1.13 inventory.push_back(atol(theToken));
|
537 rizwank 1.11 //printf("index %d, token %s, value %d\n",index,theToken,inventory[index]);
538 index++;
539 theToken = strtok (NULL,",");
540 }
|
541 rizwank 1.1
|
542 rizwank 1.13 INDEX_TYPE size_inventory = inventory.size(); //remember this is 1 based, not 0
|
543 rizwank 1.12
544 int SUPER_MODE = 0;
|
545 rizwank 1.13 if (inventory[0]==1) { SUPER_MODE=1;}
|
546 rizwank 1.1
|
547 rizwank 1.11 if (DEBUG_MODE) {
548 printf("Line 1 read - %d products from warehouse\n", size_inventory);
|
549 rizwank 1.12 if (SUPER_MODE) printf("Working in Superincreasing mode!\n");
|
550 rizwank 1.11 }
551
|
552 rizwank 1.14 // qsort ( inventory, size_inventory, sizeof(ITEM_MASS), masscomp); // we now have a sorted list
553 // sort (inventory.begin(), inventory.end(),std::greater<ITEM_MASS>() );
554 sort (inventory.begin(), inventory.end());
555 // sorts array in reverse order, biggest elements first (
|
556 rizwank 1.11 // NEED TRY/CATCH error handling for possible segfault locations
557 inputfs.getline (read_buffer, length-1);
558 ITEM_MASS palette_size=atoi(read_buffer);
559
560 if (DEBUG_MODE) {
561 printf("Line 2 read - %d weight units can fit onto palette\n",palette_size);
562 }
563
|
564 rizwank 1.13 if (SUPER_MODE) {
565 super_increase_algo (inventory, palette_size , size_inventory, DEBUG_MODE );
566 return 0;
567 }
568
|
569 rizwank 1.11 inputfs.close();
|
570 rizwank 1.12 free(read_buffer);
571
|
572 rizwank 1.11 // I could use a class to extrapolate out the file loading function like my 499 project....
573
574 backpack knapsackOne;
|
575 rizwank 1.9
|
576 rizwank 1.11 knapsackOne.initBackpack(size_inventory,palette_size);
577 if (DEBUG_MODE) {
578 printf("init %d, %d\n",size_inventory,palette_size);
579 }
580 for ( INDEX_TYPE store_index=0; size_inventory>store_index;store_index++ ) {
581 knapsackOne.putItem(inventory[store_index]);
582
583 if (DEBUG_MODE) {
584 printf("insert %d\n",inventory[store_index]);
585 }
586
587 }
|
588 rizwank 1.1 knapsackOne.store_item_array();
|
589 rizwank 1.13 inventory.clear();
|
590 rizwank 1.11 knapsackOne.branch_and_bound(DEBUG_MODE,palette_size);
|
591 rizwank 1.1
592 printf("\n");
593 }
594
595
|
596 rizwank 1.12
597
598
599
600
601
|
602 rizwank 1.1 /*
603 Modifications to the original branch-and-bound algorithim/approach
604
605 This program was to compute the maximum value that can be fit into a bag --- Using Levitin p380 for reference
606 right now. As our problem is actually a SUBSET of the given problem ,we can simplify some of the functions.
607 We also don't want any packs too small, but we'll let this compute, see how big the state tree is versus
608 an alternative algorithm.
609
610 knapsackOne.initBackpack(5,17); // 5 total items, 17 total weight
611 knapsackOne.putItem(4,1);
612 knapsackOne.putItem(7,1);
613 knapsackOne.putItem(5,1);
614 knapsackOne.putItem(9,1);
615 knapsackOne.putItem(1,1);
616
617 For given same, 2^5-1 possible nodes in tree, 14 nodes placed, 7 split.
618
619 Lets try something larger. n=10 1,2,3,4,5,6,7,8,9,10 => 18
620
621 Oooh, we can vary the max backpack item count to only use a certain amount of the items!
622
623 rizwank 1.1 Whats interesting is that we can keep the various ratio calculations, as we WOULD rather insert an item of 10 lbs rather than 1
624 We just equate weight and value later on! (Or set a fixed ratio of 1)
|
625 rizwank 1.2 knapsack insert (value,value)
626
627 This was max 2^10-1 with only 47 nodes and 33 splits.
|
628 rizwank 1.1
|
629 rizwank 1.2 And lets try with a random set of 25 numbers!
630 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
|
631 rizwank 1.5 Chose:
632 1 70 70
633 3 55 55
634 24 26 26
635 23 37 37
636 17 1 1
637 9 11 11
638 2^25-1 worst case, 142 nodes, 115 split!
639 real 0m0.036s
640 user 0m0.030s
641 sys 0m0.030s
642
|
643 rizwank 1.2
644
645
646 then 50:
647 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
|
648 rizwank 1.5 2^50 worst case, 1826 nodes, 1443 splits
649 real 0m0.044s
650 user 0m0.062s
651 sys 0m0.000s
652
|
653 rizwank 1.7
|
654 rizwank 1.5 Now, lets really ramp it up so that we can see optimzation effects
655 n=2500! won't even care to list the numbers, no point!
656
657 Wait, we exceeded 3 minutes there (our weight size was just a guess, btw, might not actually ahve a value)
658 Oh, our memory bound was maxed out so it hit a loop ... it actually completed in less than a sec! God bless my processor :)
|
659 rizwank 1.6 Lets bump it up to 5k,
660
661 Case n=5000 Total possible nodes in thie state space tree is 2^5000-1
662 Number of nodes placed in the priority queue: 35037
663 Number of nodes examined/split: 34942
664
665 real 0m2.810s
666 user 0m1.843s
667 sys 0m0.062s
668
669
670 Given that this is about the largest we can hope to achieve before INTMAX because a massive issue (we should really typedefine the container class), lets see what optimizations we can make to this code!
|
671 rizwank 1.2
|
672 rizwank 1.7 must do 1 -
|
673 rizwank 1.9 move all the ITEM_MASSs to (other)
674 the ITEM_MASSs are now ITEM_TYPE, a def earlier on (we could have done typedef here too, of course)
|
675 rizwank 1.7 real 0m2.928s
676 user 0m1.999s
677 sys 0m0.061s
678 Slight increase.
679
680 Bad things happen when we try to make it into floats, I just tired. floats can't be [] contents for an array ;p
681 Doing unsigned long for now.
682 goal 1 = stop ratio calculation and comparisons if at all possible!
683 real time shot up!
684 real 0m3.994s
685 user 0m2.390s
686 sys 0m0.046s
687
|
688 rizwank 1.8 (that being said, timse don't seem to be consistent. CVS is storing our versions, lets plow on)
689
690 remove the comparator in the structcomparator
691 real 0m2.830s
692 user 0m2.030s
693 sys 0m0.015s
694
695 remove the printout of the items as inserted
696 real 0m1.423s
697 user 0m1.436s
698 sys 0m0.015s
699
|
700 rizwank 1.9 remove the tracking of the item "number", we don't need to deal with it with this project.
701
702 after moved all unsigned ints to typedefs,
703 typedef float ITEM_MASS;
704 typedef long INDEX_TYPE;
705
706 and modified the printfs to handle floating !
707
708 real 0m1.591s
709 user 0m1.562s
710 sys 0m0.000s
711
712 inserting a float does :
713
714 acm2.cpp: In function `int main(int, char**)':
715 acm2.cpp:410: error: no matching function for call to `backpack::putItem(
716 double, int, int)'
717 acm2.cpp:279: error: candidates are: void backpack::putItem(float, float)
718 make: *** [acm2] Error 1
|
719 rizwank 1.8
|
720 rizwank 1.9 (and it locks up if we have a decimal in seeked value)
|
721 rizwank 1.8
|
722 rizwank 1.10 ok we move onwards to remove weight,value calls and replace them with just weight
723 we also use notepad/sed to remove half the sample knapsack calls
724 we realize in doing this that we've actually got 7009 elements! modifiying appropraite values!
725
726 real 0m2.627s
727 user 0m2.624s
728 sys 0m0.000s
729
730 but now it uses all 17.
731
732
733 Lets try an appropriately high value instead of the 50000ish we're using now. Lets say, we want ...
734 600 elements of 7000, at avg value of 5000 3000000ish?
735
736 Case n=6998 Total possible nodes in thie state space tree is 2^6998-1
737 Number of nodes placed in the priority queue: 70797
738 Number of nodes examined/split: 69811
739
740 Totals: 114 509283.00 509283.00
741
742 then...
743 rizwank 1.10
744 ============================ KNAPSACK ONE ================================
745 Case n=6998 Total possible nodes in thie state space tree is 2^6998-1
746 Number of nodes placed in the priority queue: 108848
747 Number of nodes examined/split: 96391
748
749 Totals: 1002 5091283.00 5091283.00
750
751
752 real 0m9.526s
753 user 0m9.249s
754 sys 0m0.203s
755
756
757 I'm actually pretty happy with this. We havent tested a few conditions, but its time we got the file loading routine in
758
759
760 todo
761 1) when it doesnt work
762 2) when its already reached stop
763 3) float
764 rizwank 1.10
|
765 rizwank 1.11 For superincreasing sets, its INCREDIBLY easy to do
766 Sort it.
767 if (current value < pallete size), palletsize-current value, current_value on board.
768 repeat until end
769
770
771
772 === loading file now
773 make input float ok
774
775 reverted to base type of non float --- making the stored value float did badthings to atoi / atof (they didnt work)
|
776 rizwank 1.10
|
777 rizwank 1.8
778 we could really move the pqueue to a queue --- although don't we want to push bigger items to the top to fill it up faster?
|
779 rizwank 1.7
780 goal 1 - lets remove the double call to the creator function, weight=value ratio=1
|
781 rizwank 1.2
|
782 rizwank 1.14
783 large set time :
784 103,199,67,119,152,119,181,85,74,73,130,82,79,98,99,95,101,81,54,129,157,88,177,97,122,74,46,77,142,39,61,13,86,173,83,180,49,196,144,101,43,28,3,139,127,149,64,194,18,168,75,89,110,113,113,183,124,4,143,61,70,162,161,101,75,47,51,28,4,149,44,58,131,36,53,18,118,89,37,12,99,38,189,98,164,65,109,190,103,113,160,51,113,130,113,50,26,138,153,196,80,193,40,197,52,195,190,97,108,111,141,2,180,5,125,139,38,21,60,148,191,158,169,50,155,167,152,25,154,3,11,1
785
786 real 1m14.327s
787 user 1m11.530s
788 sys 0m0.421s
789
790 with goto removed.
791
792
793 largeset time with early leave!
794 Early value acquired! 13273
795 133,103,105,199,33,67,119,119,181,85,74,73,26,130,82,79,98,99,95,101,81,54,129,157,88,177,97,122,74,46,77,142,39,61,13,86,173,83,180,49,196,144,101,43,28,3,139,127,149,64,194,18,168,75,89,110,113,113,183,124,4,143,61,70,162,161,101,75,47,51,28,4,149,44,58,131,36,53,18,118,89,37,12,99,38,189,98,164,65,109,190,103,113,160,51,113,130,113,50,26,138,153,196,80,193,40,197,52,195,190,97,108,111,141,2,180,5,53,125,139,38,21,60,148,191,158,169,50,155,167,25,86,24,3,10
796
797 real 0m2.594s
798 user 0m2.093s
799 sys 0m0.468s
800
801 Case n=4555 Total possible nodes in thie state space tree is 2^4555-1
802 Number of nodes placed in the priority queue: 45994
803 rizwank 1.14 Number of nodes examined/split: 45381
804
805 real 1m5.247s
806 user 1m3.374s
807 sys 0m0.327s
808 after a presort. What about decsending sort?
809
810 note, removing -g only kills a 1 second or something
811
812 real 0m2.446s
813 user 0m2.186s
814 sys 0m0.203s
815
816 with presort and early out
|
817 rizwank 1.1
818 */
819
|
Return to
acm2.cpp
CVS log
Up to [RizwankCVS] / acm