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