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