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.1 #include <stdio.h>
|
8 rizwank 1.11 // yes I could use just one i/o lib
9 using namespace std;
10
|
11 rizwank 1.1
12 // As per specification, the project has to be able to grow to an
13 // arbitrary amount of items. MAX_ITEMS describes the size of the
14 // appropriate arrays and must be changed at compile time.
15 // (dynamically created arrays had their pointers corrupted when
16 // their parent object was in the priority queue, so static sized
17 // arrays were used
18
|
19 rizwank 1.12 #define MAX_ITEMS 65536
20 //the above bound comes from the fixed value for the boolean array TODO REMOVE LIMITATION
|
21 rizwank 1.1
|
22 rizwank 1.11 typedef long ITEM_MASS;
|
23 rizwank 1.9 typedef long INDEX_TYPE;
24
25
|
26 rizwank 1.1 using namespace std;
27
28 // ******************************************************************
29 // * CLASS : item *
30 // * Container object with all the data for a particular item *
31 // ******************************************************************
32 class item {
33 public:
|
34 rizwank 1.8 // float getRatio();
|
35 rizwank 1.9 ITEM_MASS getWeight();
36 ITEM_MASS getCost();
37 // ITEM_MASS getNumber();
|
38 rizwank 1.10 void setData(ITEM_MASS);
|
39 rizwank 1.1 private:
|
40 rizwank 1.9 ITEM_MASS weight;
41 ITEM_MASS cost;
|
42 rizwank 1.8 // float ratio;
|
43 rizwank 1.9 // ITEM_MASS number;
|
44 rizwank 1.1 };
45
46 // ******************************************************************
47 // * CLASS : backpack *
48 // * Container object with all the data for an entire knapsack *
49 // * Full declaration follows, partial declare here for key *
50 // ******************************************************************
51 class backpack;
52
53 // ******************************************************************
54 // * CLASS : key *
55 // * Container object with all the data for the equivalent of a node*
56 // * on the state space tree *
57 // * To allow data to remain private (and decrease the need of data *
58 // * such as max_weight and total_items to be passed along with *
59 // * every function call, a pointer to the containing backpack is *
60 // * instead implemented. *
61 // ******************************************************************
62 class key {
63 public:
64 void initKey( backpack *);
65 rizwank 1.1 void flagNext();
66 void addCurItem();
67 bool doneItems();
68 float getBound();
|
69 rizwank 1.9 bool checkItem(INDEX_TYPE);
70 ITEM_MASS getWeight();
71 ITEM_MASS getValue();
|
72 rizwank 1.1 private:
73 void calcBound();
74 bool inserted[MAX_ITEMS];
|
75 rizwank 1.9 INDEX_TYPE nextitem;
76 ITEM_MASS cur_weight;
77 ITEM_MASS cur_value;
|
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->cur_value=0;
135 this->calcBound();
136 }
137
138 // ******************************************************************
139 // * FUNCTION : flagNext IN : CLASS key *
140 // * Modifies the key by setting the next item as not inserted but *
141 rizwank 1.1 // * as processed, then updates the bound. *
142 // ******************************************************************
143 void key::flagNext(){
144 this->inserted[this->nextitem]=0;
145 nextitem++;
146 this->calcBound();
147 }
148
149 // ******************************************************************
150 // * FUNCTION : addCurItem IN : CLASS key *
151 // * Follows up flagNext by actually marking the last item as *
152 // * inserted, adding values and weights, then recalcing the bound. *
153 // ******************************************************************
154 void key::addCurItem(){
155 nextitem--;
156 this->inserted[this->nextitem]=1;
157 this->cur_value += (this->myBackpack->get_Item(this->nextitem)).getCost();
158 this->cur_weight += (this->myBackpack->get_Item(this->nextitem)).getWeight();
159 nextitem++;
160 this->calcBound();
161 }
162 rizwank 1.1
163 // ******************************************************************
164 // * FUNCTION : doneItems IN : CLASS key *
165 // * Returns TRUE if all the items have been processed *
166 // ******************************************************************
167 bool key::doneItems(){
168 return ( this->myBackpack->get_totalItems() == this->nextitem );
169 }
170
171 // ******************************************************************
172 // * FUNCTION : getBound IN : CLASS key *
173 // * Returns the bound. *
174 // ******************************************************************
175 float key::getBound(){
176 return this->upper_bound;
177 }
178
179 // ******************************************************************
180 // * FUNCTION : calcBound IN : CLASS key *
181 // * Calculates the bound. If there are no more items, the bound *
182 // * remains unchanged. Else, perform the calcuations. *
183 rizwank 1.1 // * If the weight is over max_weight, set the bound to 0 *
184 // ******************************************************************
185 void key::calcBound(){
186 float temp;
187 if (this->doneItems()) {
188 temp = 0;
189 }
190 else {
191 temp = (float)((this->myBackpack->get_maxWeight()) - cur_weight);
|
192 rizwank 1.7 // temp = temp * (this->myBackpack->get_Item(this->nextitem)).getRatio(); (ratio = 1!)
|
193 rizwank 1.1 }
194 this->upper_bound = cur_value + temp;
195
196 // What about if the bag is overloaded?
197 if (this->cur_weight > this->myBackpack->get_maxWeight()){
198 this->upper_bound = 0; // invalidate it, will never reach 0 in bound
199 }
200 }
201
202
203 // ******************************************************************
204 // * FUNCTION : checkItem IN : CLASS key *
205 // * Checks if a given item is listed as inserted. *
206 // ******************************************************************
|
207 rizwank 1.9 bool key::checkItem(INDEX_TYPE num) {
|
208 rizwank 1.1 return (this->inserted[num]);
209 }
210
211 // ******************************************************************
212 // * FUNCTION : getValue IN : CLASS key *
213 // * Gets the Value of the current key. *
214 // ******************************************************************
|
215 rizwank 1.9 ITEM_MASS key::getValue(){
|
216 rizwank 1.1 return this->cur_value;
217 }
218
219 // ******************************************************************
220 // * FUNCTION : getWeight IN : CLASS key *
221 // * Gets the Weight of the current key. *
222 // ******************************************************************
|
223 rizwank 1.9 ITEM_MASS key::getWeight(){
|
224 rizwank 1.1 return this->cur_weight;
225 }
226
227 // ******************************************************************
228 // * FUNCTION : getRatio IN : CLASS item *
229 // * Gets the Ratio for the current item. *
230 // ******************************************************************
|
231 rizwank 1.8 //float item::getRatio(){
232 // return ratio;
233 //}
|
234 rizwank 1.1
235 // ******************************************************************
236 // * FUNCTION : getWeight IN : CLASS item *
237 // * Gets the Weight of the current item. *
238 // ******************************************************************
|
239 rizwank 1.9 ITEM_MASS item::getWeight(){
|
240 rizwank 1.1 return this->weight;
241 }
242
243 // ******************************************************************
244 // * FUNCTION : getCost IN : CLASS item *
245 // * Gets the Value of the current item. *
246 // ******************************************************************
|
247 rizwank 1.9 ITEM_MASS item::getCost(){
|
248 rizwank 1.1 return this->cost;
249 }
250
251 // ******************************************************************
252 // * FUNCTION : getNumber IN : CLASS item *
253 // * Gets the Index of the current item. *
254 // ******************************************************************
|
255 rizwank 1.9 //ITEM_MASS item::getNumber(){
256 // return this->number;
257 //}
|
258 rizwank 1.1
259 // ******************************************************************
260 // * FUNCTION : setData IN : CLASS item *
261 // * Sets all the data for an item. *
262 // ******************************************************************
|
263 rizwank 1.10 void item::setData(ITEM_MASS weightage){ //, ITEM_MASS costage, ITEM_MASS numerage){
264 this->cost = weightage; //costage;
|
265 rizwank 1.1 this->weight = weightage;
|
266 rizwank 1.7 // this->ratio = ( (float)(cost)/(float)(weight) );
|
267 rizwank 1.8 // this->ratio = 1; //ratio = 1
|
268 rizwank 1.9 // this->number = numerage;
|
269 rizwank 1.1 }
270
271
272 // ******************************************************************
273 // * FUNCTION : initBackpack IN : CLASS backpack *
274 // * Initalizes the backpack values and creates the item array *
275 // ******************************************************************
|
276 rizwank 1.9 void backpack::initBackpack(INDEX_TYPE total, ITEM_MASS max){
|
277 rizwank 1.1 this->totalItems = total;
278 this->maxWeight = max;
279 item_array = new item[total];
280 worknodeCount = 0;
281 addnodeCount = 0;
282 }
283
284 // ******************************************************************
285 // * FUNCTION : putItem IN : CLASS backpack *
286 // * Creates an item and places it into the priority queue *
287 // ******************************************************************
|
288 rizwank 1.10 void backpack::putItem(ITEM_MASS weight){ //, ITEM_MASS cost){
|
289 rizwank 1.1 item temp_item;
|
290 rizwank 1.10 temp_item.setData(weight);//,cost);//,(int)(this->item_queue.size())+1); // sometimes this starts at 2000?
|
291 rizwank 1.1 this->item_queue.push(temp_item);
292 }
293
294 // ******************************************************************
295 // * FUNCTION : store_item_array IN : CLASS backpack *
296 // * Dumps the Item Queue in order into an Array for Rand. Access *
297 // ******************************************************************
298 void backpack::store_item_array(){
299 this->item_array = new item[this->totalItems];
300 for ( int i = 0; this->totalItems > i; i++){
301 this->item_array[i] = this->item_queue.top();
302 this->item_queue.pop();
303 }
304 }
305
306 // ******************************************************************
307 // * FUNCTION : get_totalItems IN : CLASS backpack *
308 // * Returns the number of items for consideration. *
309 // ******************************************************************
|
310 rizwank 1.9 ITEM_MASS backpack::get_totalItems(){
|
311 rizwank 1.1 return this->totalItems;
312 }
313
314 // ******************************************************************
315 // * FUNCTION : get_maxWeight IN : CLASS backpack *
316 // * Returns the maximum weight for this backpack. *
317 // ******************************************************************
|
318 rizwank 1.9 ITEM_MASS backpack::get_maxWeight(){
|
319 rizwank 1.1 return this->maxWeight;
320 }
321
322 // ******************************************************************
323 // * FUNCTION : get_Item IN : CLASS backpack *
324 // * Returns a particular item from the item array *
325 // ******************************************************************
|
326 rizwank 1.9 item backpack::get_Item(INDEX_TYPE index){
|
327 rizwank 1.1 return ( this->item_array[index] );
328 }
329
330 // ******************************************************************
331 // * FUNCTION : branch_and_bound IN : CLASS backpack *
332 // * Performs Best-First-Fit Branch and Bound on this backpack *
333 // * while keeping track of the nodecounts. *
334 // * Create a template key with the best possible bound. *
335 // * Place that key into the queue and start a loop *
336 // * As long as the 'onwards' flag is TRUE, repeat: *
337 // * Take the topmost (highest bound) key out of the queue. *
338 // * If that bound has all of its items processed, clear ownards *
339 // * Else, create two keys from the original key *
340 // * One without the next item and one with. *
341 // * Place the new keys into the queue and discard the current *
342 // * Repeat *
343 // * If the loop is ended, the top item on the queue is the best *
344 // * possible solution for this knapsack. *
345 // * Fetch all the information and print it out. *
346 // ******************************************************************
|
347 rizwank 1.11 void backpack::branch_and_bound(int DEBUG_MODE, ITEM_MASS targetvalue){
|
348 rizwank 1.1 key temp_key;
349
350 temp_key.initKey(this);
351 this->key_queue.push(temp_key);
352 this->addnodeCount++;
353
354 bool onwards = 1;
355
356 do
357 {
358 temp_key = key_queue.top();
359 this->key_queue.pop();
360 if ( temp_key.doneItems() ) {
361 onwards = 0;
362 }
363 else {
364 this->worknodeCount++;
365 temp_key.flagNext();
366 this->key_queue.push(temp_key);
367 this->addnodeCount++;
368 temp_key.addCurItem();
369 rizwank 1.1 if (temp_key.getBound() != 0){
370 this->key_queue.push(temp_key);
371 this->addnodeCount++;
372 }
373 }
374 }
375 while (onwards);
376
377
|
378 rizwank 1.11 if (DEBUG_MODE) {
379 printf("Case n=%2d Total possible nodes in thie state space tree is 2^%2d-1\n",this->totalItems,this->totalItems);
380 printf(" Number of nodes placed in the priority queue: %6d\n",this->addnodeCount);
381 printf(" Number of nodes examined/split: %6d\n",this->worknodeCount);
382 /* printf("\nObjects Chosen \n");
383
384 printf("\t\tWeights\tValues\n");
385 int totalitemsinserted = 0;
386 for (int i = 0; this->totalItems > i; i++) {
387 if ( temp_key.checkItem(i) ) {
388 printf("\t\t%4.2f\t%4.2f\n", this->item_array[i].getWeight(), this->item_array[i].getCost());
389 totalitemsinserted++; // this->item_array[i].getNumber(), removed
390 }
391 }
392 printf("======================================================\n");
393 printf("Totals:\t%3d\t%4.2f\t%4.2f\n",totalitemsinserted, temp_key.getWeight(), temp_key.getValue());
394 // printf("Ratio : %2.5f\n", ((float)temp_key.getValue()/(float)temp_key.getWeight())); */
395 }
396
397
|
398 rizwank 1.12 if ( temp_key.getWeight() == targetvalue ) {
|
399 rizwank 1.11 int totalitemsinserted = 0;
400 int first=1;
401 for (int i = 0; this->totalItems > i; i++) {
402 if ( temp_key.checkItem(i) ) {
403 if (first==0) { printf(","); }
404 else {first = 0;} // there has GOT to be a better way!
405 printf("%d", this->item_array[i].getWeight());
406 }
407 }
|
408 rizwank 1.12 }
409 else { printf("CANNOT FILL PALLET\n"); }
|
410 rizwank 1.11 }
|
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 rizwank 1.12 ITEM_MASS * inventory = (ITEM_MASS *) malloc (length);
480 // could use stack instead of array --- doesn't require malloc, more 'safe' avoids overflows, esp if
481 // input file is funky --- its better software engineering, but its slower. Given that this is a pretty
482 // small system, I'll stick with the array
|
483 rizwank 1.11 inputfs.getline (read_buffer, length-1);
484
485 char * theToken; INDEX_TYPE index = 0;
486 theToken=strtok(read_buffer,",");
487 // assume 1+ items
488 while ( theToken != NULL ) {
489 //printf("tokendebug %d %f\n",theToken,theToken);
490 inventory[index] = atol(theToken);
491 //printf("index %d, token %s, value %d\n",index,theToken,inventory[index]);
492 index++;
493 theToken = strtok (NULL,",");
494 }
|
495 rizwank 1.1
|
496 rizwank 1.11 INDEX_TYPE size_inventory = index; //remember this is 1 based, not 0
|
497 rizwank 1.12
498 int SUPER_MODE = 0;
499 if (inventory[0]==1) { SUPER_MODE=0;}
|
500 rizwank 1.1
|
501 rizwank 1.11 if (DEBUG_MODE) {
502 printf("Line 1 read - %d products from warehouse\n", size_inventory);
|
503 rizwank 1.12 if (SUPER_MODE) printf("Working in Superincreasing mode!\n");
|
504 rizwank 1.11 }
505
506 // qsort ( inventory, size_inventory, sizeof(int), intcomp); // we now have a sorted list
507 // NEED TRY/CATCH error handling for possible segfault locations
508 inputfs.getline (read_buffer, length-1);
509 ITEM_MASS palette_size=atoi(read_buffer);
510
511 if (DEBUG_MODE) {
512 printf("Line 2 read - %d weight units can fit onto palette\n",palette_size);
513 }
514
515 inputfs.close();
|
516 rizwank 1.12 free(read_buffer);
517
518 if
519
|
520 rizwank 1.11
521 // ckeanup, release memeory, close files here
|
522 rizwank 1.9
523
|
524 rizwank 1.11 // I could use a class to extrapolate out the file loading function like my 499 project....
525
526 backpack knapsackOne;
|
527 rizwank 1.9
|
528 rizwank 1.11 knapsackOne.initBackpack(size_inventory,palette_size);
529 if (DEBUG_MODE) {
530 printf("init %d, %d\n",size_inventory,palette_size);
531 }
532 for ( INDEX_TYPE store_index=0; size_inventory>store_index;store_index++ ) {
533 knapsackOne.putItem(inventory[store_index]);
534
535 if (DEBUG_MODE) {
536 printf("insert %d\n",inventory[store_index]);
537 }
538
539 }
|
540 rizwank 1.1 knapsackOne.store_item_array();
|
541 rizwank 1.12 free(inventory);
|
542 rizwank 1.11 knapsackOne.branch_and_bound(DEBUG_MODE,palette_size);
|
543 rizwank 1.1
544 printf("\n");
545 }
546
547
|
548 rizwank 1.12
549
550 void super ( ITEM_MASS target_value , INDEX_TYPE size_inventory, int DEBUG_MODE ) {
551 // input, a super increasing set, lowest to highest.
552 // the number of elements in the list [1-ordinal]
553 // a target value.
554 //debugmode
555
556 // need to output values that sum to target
557 // need another place to store. --- not another array, need LIFO structure. A stack of course.
558 // we have to count downwards during super increasing, or we could qsort the list. (not going to do that)
559
560 stack<ITEM_MASS> packages_to_load;
561
562 if (DEBUG_MODE) {
563 printf("Extracting values, highest to lowest, doing reduction\n");
564 }
565 for ( INDEX_TYPE store_index=size_inventory-1; size_inventory<=0;store_index-- ) {
566 if (DEBUG_MODE) {
567 printf("value %d, is it smaller than %d? If so, subtract and store.\n",inventory[store_index],target_value);
568 }
569 rizwank 1.12 if ( inventory[store_index] <= target_value ) {
570 target_value = target_value - inventory[store_index];
571 packages_to_load.push(inventory[store_index]);
572 }
573 }
574 if ( target_value == 0 ) {
575 int first = 1;
576 while ( ! packages_to_load.empty() ) {
577 if (first==0) { printf(","); }
578 else {first = 0;} // there has GOT to be a better way!
579 printf("%d",packages_to_load.top());
580 packages_to_load.pop();
581 }
582 else { printf("CANNOT FILL PALLET\n"); }
583
584
585 }
586
587
588
589
|
590 rizwank 1.1 /*
591 Modifications to the original branch-and-bound algorithim/approach
592
593 This program was to compute the maximum value that can be fit into a bag --- Using Levitin p380 for reference
594 right now. As our problem is actually a SUBSET of the given problem ,we can simplify some of the functions.
595 We also don't want any packs too small, but we'll let this compute, see how big the state tree is versus
596 an alternative algorithm.
597
598 knapsackOne.initBackpack(5,17); // 5 total items, 17 total weight
599 knapsackOne.putItem(4,1);
600 knapsackOne.putItem(7,1);
601 knapsackOne.putItem(5,1);
602 knapsackOne.putItem(9,1);
603 knapsackOne.putItem(1,1);
604
605 For given same, 2^5-1 possible nodes in tree, 14 nodes placed, 7 split.
606
607 Lets try something larger. n=10 1,2,3,4,5,6,7,8,9,10 => 18
608
609 Oooh, we can vary the max backpack item count to only use a certain amount of the items!
610
611 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
612 We just equate weight and value later on! (Or set a fixed ratio of 1)
|
613 rizwank 1.2 knapsack insert (value,value)
614
615 This was max 2^10-1 with only 47 nodes and 33 splits.
|
616 rizwank 1.1
|
617 rizwank 1.2 And lets try with a random set of 25 numbers!
618 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
|
619 rizwank 1.5 Chose:
620 1 70 70
621 3 55 55
622 24 26 26
623 23 37 37
624 17 1 1
625 9 11 11
626 2^25-1 worst case, 142 nodes, 115 split!
627 real 0m0.036s
628 user 0m0.030s
629 sys 0m0.030s
630
|
631 rizwank 1.2
632
633
634 then 50:
635 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
|
636 rizwank 1.5 2^50 worst case, 1826 nodes, 1443 splits
637 real 0m0.044s
638 user 0m0.062s
639 sys 0m0.000s
640
|
641 rizwank 1.7
|
642 rizwank 1.5 Now, lets really ramp it up so that we can see optimzation effects
643 n=2500! won't even care to list the numbers, no point!
644
645 Wait, we exceeded 3 minutes there (our weight size was just a guess, btw, might not actually ahve a value)
646 Oh, our memory bound was maxed out so it hit a loop ... it actually completed in less than a sec! God bless my processor :)
|
647 rizwank 1.6 Lets bump it up to 5k,
648
649 Case n=5000 Total possible nodes in thie state space tree is 2^5000-1
650 Number of nodes placed in the priority queue: 35037
651 Number of nodes examined/split: 34942
652
653 real 0m2.810s
654 user 0m1.843s
655 sys 0m0.062s
656
657
658 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!
|
659 rizwank 1.2
|
660 rizwank 1.7 must do 1 -
|
661 rizwank 1.9 move all the ITEM_MASSs to (other)
662 the ITEM_MASSs are now ITEM_TYPE, a def earlier on (we could have done typedef here too, of course)
|
663 rizwank 1.7 real 0m2.928s
664 user 0m1.999s
665 sys 0m0.061s
666 Slight increase.
667
668 Bad things happen when we try to make it into floats, I just tired. floats can't be [] contents for an array ;p
669 Doing unsigned long for now.
670 goal 1 = stop ratio calculation and comparisons if at all possible!
671 real time shot up!
672 real 0m3.994s
673 user 0m2.390s
674 sys 0m0.046s
675
|
676 rizwank 1.8 (that being said, timse don't seem to be consistent. CVS is storing our versions, lets plow on)
677
678 remove the comparator in the structcomparator
679 real 0m2.830s
680 user 0m2.030s
681 sys 0m0.015s
682
683 remove the printout of the items as inserted
684 real 0m1.423s
685 user 0m1.436s
686 sys 0m0.015s
687
|
688 rizwank 1.9 remove the tracking of the item "number", we don't need to deal with it with this project.
689
690 after moved all unsigned ints to typedefs,
691 typedef float ITEM_MASS;
692 typedef long INDEX_TYPE;
693
694 and modified the printfs to handle floating !
695
696 real 0m1.591s
697 user 0m1.562s
698 sys 0m0.000s
699
700 inserting a float does :
701
702 acm2.cpp: In function `int main(int, char**)':
703 acm2.cpp:410: error: no matching function for call to `backpack::putItem(
704 double, int, int)'
705 acm2.cpp:279: error: candidates are: void backpack::putItem(float, float)
706 make: *** [acm2] Error 1
|
707 rizwank 1.8
|
708 rizwank 1.9 (and it locks up if we have a decimal in seeked value)
|
709 rizwank 1.8
|
710 rizwank 1.10 ok we move onwards to remove weight,value calls and replace them with just weight
711 we also use notepad/sed to remove half the sample knapsack calls
712 we realize in doing this that we've actually got 7009 elements! modifiying appropraite values!
713
714 real 0m2.627s
715 user 0m2.624s
716 sys 0m0.000s
717
718 but now it uses all 17.
719
720
721 Lets try an appropriately high value instead of the 50000ish we're using now. Lets say, we want ...
722 600 elements of 7000, at avg value of 5000 3000000ish?
723
724 Case n=6998 Total possible nodes in thie state space tree is 2^6998-1
725 Number of nodes placed in the priority queue: 70797
726 Number of nodes examined/split: 69811
727
728 Totals: 114 509283.00 509283.00
729
730 then...
731 rizwank 1.10
732 ============================ KNAPSACK ONE ================================
733 Case n=6998 Total possible nodes in thie state space tree is 2^6998-1
734 Number of nodes placed in the priority queue: 108848
735 Number of nodes examined/split: 96391
736
737 Totals: 1002 5091283.00 5091283.00
738
739
740 real 0m9.526s
741 user 0m9.249s
742 sys 0m0.203s
743
744
745 I'm actually pretty happy with this. We havent tested a few conditions, but its time we got the file loading routine in
746
747
748 todo
749 1) when it doesnt work
750 2) when its already reached stop
751 3) float
752 rizwank 1.10
|
753 rizwank 1.11 For superincreasing sets, its INCREDIBLY easy to do
754 Sort it.
755 if (current value < pallete size), palletsize-current value, current_value on board.
756 repeat until end
757
758
759
760 === loading file now
761 make input float ok
762
763 reverted to base type of non float --- making the stored value float did badthings to atoi / atof (they didnt work)
|
764 rizwank 1.10
|
765 rizwank 1.8
766 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?
|
767 rizwank 1.7
768 goal 1 - lets remove the double call to the creator function, weight=value ratio=1
|
769 rizwank 1.2
|
770 rizwank 1.1
771 */
772
|
Return to
acm2.cpp
CVS log
Up to [RizwankCVS] / acm