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