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