(file) Return to acm2.cpp CVS log (file) (dir) Up to [RizwankCVS] / acm

  1 rizwank 1.1 #include <queue>
  2             #include <stdio.h>
  3             
  4             // As per specification, the project has to be able to grow to an 
  5             // arbitrary amount of items. MAX_ITEMS describes the size of the
  6             // appropriate arrays and must be changed at compile time.
  7             // (dynamically created arrays had their pointers corrupted when 
  8             // their parent object was in the priority queue, so static sized
  9             // arrays were used
 10             
 11 rizwank 1.2 #define MAX_ITEMS 55
 12 rizwank 1.1 
 13             using namespace std;
 14             
 15             // ******************************************************************
 16             // * CLASS : item													*
 17             // * Container object with all the data for a particular item		*
 18             // ******************************************************************
 19             class item {
 20             public:
 21             	float getRatio();
 22             	unsigned short getWeight();
 23                 unsigned short getCost();
 24             	unsigned short getNumber();
 25             	void setData(unsigned short,unsigned short,unsigned short);
 26             private:
 27             	unsigned short weight;
 28             	unsigned short cost;
 29             	float ratio;
 30             	unsigned short number;
 31             };
 32             
 33 rizwank 1.1 // ******************************************************************
 34             // * CLASS : backpack												*
 35             // * Container object with all the data for an entire knapsack		*
 36             // * Full declaration follows, partial declare here for key			*
 37             // ******************************************************************
 38             class backpack;
 39             
 40             // ******************************************************************
 41             // * CLASS : key													*
 42             // * Container object with all the data for the equivalent of a node*
 43             // * on the state space tree										*
 44             // * To allow data to remain private (and decrease the need of data *
 45             // * such as max_weight and total_items to be passed along with		*
 46             // * every function call, a pointer to the containing backpack is	*
 47             // * instead implemented.											*
 48             // ******************************************************************
 49             class key {
 50             public:
 51             	void initKey( backpack *);
 52             	void flagNext();
 53             	void addCurItem();
 54 rizwank 1.1 	bool doneItems();
 55             	float getBound();
 56             	bool checkItem(unsigned short);
 57             	unsigned short getWeight();
 58             	unsigned short getValue();
 59             private:
 60             	void calcBound();
 61             	bool inserted[MAX_ITEMS];
 62             	unsigned short nextitem;
 63             	unsigned short cur_weight;
 64             	unsigned short cur_value;
 65             	float upper_bound;
 66             	backpack *myBackpack;
 67             };
 68             
 69             // ******************************************************************
 70             // * STRUCT : item_comparator										*
 71             // * Functor for comparing the ratio between items					*
 72             // ******************************************************************
 73             struct item_comparator {
 74             	bool operator()( item left, item right ) const 
 75 rizwank 1.1 	{ return ( left.getRatio() < right.getRatio() ) ; } 
 76             } ;
 77             
 78             // ******************************************************************
 79             // * STRUCT : key_comparator										*
 80             // * Functor for comparing the bound between items					*
 81             // ******************************************************************
 82             struct key_comparator {
 83             	bool operator()( key left, key right ) const 
 84             	{ return ( left.getBound() < right.getBound() ) ; } 
 85             } ;
 86             
 87             // ******************************************************************
 88             // * CLASS : backpack												*
 89             // * Container object with all the data for an entire knapsack		*
 90             // ******************************************************************
 91             class backpack {
 92             public:
 93             	void initBackpack(unsigned short, unsigned short);
 94             	void putItem(unsigned short, unsigned short);
 95             	void store_item_array();
 96 rizwank 1.1 	void branch_and_bound();
 97             	unsigned short get_totalItems();
 98             	unsigned short get_maxWeight();
 99             	item get_Item(unsigned short);
100             private:
101             	priority_queue< item, vector<item> , item_comparator> item_queue;
102             	item *item_array;
103             	priority_queue< key, vector<key>, key_comparator> key_queue;
104             	unsigned short totalItems;
105             	unsigned short maxWeight;
106             	long addnodeCount, worknodeCount;
107             };
108             
109             
110             
111             // ******************************************************************
112             // * FUNCTION : initKey		IN : CLASS key							*
113             // * Initalizes a key, setting the backpack pointer and inital		*
114             // * values then calculating the bound.								*
115             // ******************************************************************
116             void key::initKey(backpack *theCaller){
117 rizwank 1.1 	this->myBackpack = theCaller;
118             	this->nextitem=0;
119             	this->cur_weight=0;
120             	this->cur_value=0;
121             	this->calcBound();
122             }
123             
124             // ******************************************************************
125             // * FUNCTION : flagNext		IN : CLASS key						*
126             // * Modifies the key by setting the next item as not inserted but	*
127             // * as processed, then updates the bound.							*
128             // ******************************************************************
129             void key::flagNext(){
130             	this->inserted[this->nextitem]=0;
131             	nextitem++;
132             	this->calcBound();
133             }
134             
135             // ******************************************************************
136             // * FUNCTION : addCurItem		IN : CLASS key						*
137             // * Follows up flagNext by actually marking the last item as		*
138 rizwank 1.1 // * inserted, adding values and weights, then recalcing the bound.	*
139             // ******************************************************************
140             void key::addCurItem(){
141             	nextitem--;
142             	this->inserted[this->nextitem]=1;
143             	this->cur_value  += (this->myBackpack->get_Item(this->nextitem)).getCost();
144             	this->cur_weight += (this->myBackpack->get_Item(this->nextitem)).getWeight();
145             	nextitem++;
146             	this->calcBound();
147             }
148             
149             // ******************************************************************
150             // * FUNCTION : doneItems		IN : CLASS key						*
151             // * Returns TRUE if all the items have been processed				*
152             // ******************************************************************
153             bool key::doneItems(){
154             	return ( this->myBackpack->get_totalItems() == this->nextitem );
155             }
156             
157             // ******************************************************************
158             // * FUNCTION : getBound		IN : CLASS key						*
159 rizwank 1.1 // * Returns the bound.												*
160             // ******************************************************************
161             float key::getBound(){
162             	return this->upper_bound;
163             }
164             
165             // ******************************************************************
166             // * FUNCTION : calcBound		IN : CLASS key						*
167             // * Calculates the bound. If there are no more items, the bound	*
168             // * remains unchanged. Else, perform the calcuations.				*
169             // * If the weight is over max_weight, set the bound to 0			*
170             // ******************************************************************
171             void key::calcBound(){
172             	float temp;
173             	if (this->doneItems()) {
174             		temp = 0;
175             	}
176             	else {
177             		temp = (float)((this->myBackpack->get_maxWeight()) - cur_weight);
178             		temp = temp * (this->myBackpack->get_Item(this->nextitem)).getRatio();
179             	}
180 rizwank 1.1 	this->upper_bound = cur_value + temp;
181             
182             	// What about if the bag is overloaded?
183             	if (this->cur_weight > this->myBackpack->get_maxWeight()){
184             		this->upper_bound = 0;		// invalidate it, will never reach 0 in bound
185             	}
186             }
187             
188             
189             // ******************************************************************
190             // * FUNCTION : checkItem		IN : CLASS key						*
191             // * Checks if a given item is listed as inserted.					*
192             // ******************************************************************
193             bool key::checkItem(unsigned short num) {
194             	return (this->inserted[num]);
195             }
196             
197             // ******************************************************************
198             // * FUNCTION : getValue		IN : CLASS key						*
199             // * Gets the Value of the current key.								*
200             // ******************************************************************
201 rizwank 1.1 unsigned short key::getValue(){
202             	return this->cur_value;
203             }
204             
205             // ******************************************************************
206             // * FUNCTION : getWeight		IN : CLASS key						*
207             // * Gets the Weight of the current key.							*
208             // ******************************************************************
209             unsigned short key::getWeight(){
210             	return this->cur_weight;
211             }
212             
213             // ******************************************************************
214             // * FUNCTION : getRatio		IN : CLASS item						*
215             // * Gets the Ratio for the current item.							*
216             // ******************************************************************
217             float item::getRatio(){
218             	return ratio;
219             }
220             
221             // ******************************************************************
222 rizwank 1.1 // * FUNCTION : getWeight		IN : CLASS item						*
223             // * Gets the Weight of the current item.							*
224             // ******************************************************************
225             unsigned short item::getWeight(){
226             	return this->weight;
227             }
228             
229             // ******************************************************************
230             // * FUNCTION : getCost			IN : CLASS item						*
231             // * Gets the Value of the current item.							*
232             // ******************************************************************
233             unsigned short item::getCost(){
234             	return this->cost;
235             }
236             
237             // ******************************************************************
238             // * FUNCTION : getNumber		IN : CLASS item						*
239             // * Gets the Index of the current item.							*
240             // ******************************************************************
241             unsigned short item::getNumber(){
242             	return this->number;
243 rizwank 1.1 }
244             
245             // ******************************************************************
246             // * FUNCTION : setData			IN : CLASS item						*
247             // * Sets all the data for an item.									*
248             // ******************************************************************
249             void item::setData(unsigned short weightage, unsigned short costage, unsigned short numerage){
250             	this->cost = costage;
251             	this->weight = weightage;
252             	this->ratio = ( (float)(cost)/(float)(weight) );
253             	this->number = numerage;
254             }
255             
256             
257             // ******************************************************************
258             // * FUNCTION : initBackpack	IN : CLASS backpack					*
259             // * Initalizes the backpack values and creates the item array		*
260             // ******************************************************************
261             void backpack::initBackpack(unsigned short total, unsigned short max){
262             	this->totalItems = total;
263             	this->maxWeight = max;
264 rizwank 1.1 	item_array = new item[total];
265             	worknodeCount = 0;
266             	addnodeCount = 0;
267             }
268             
269             // ******************************************************************
270             // * FUNCTION : putItem			IN : CLASS backpack					*
271             // * Creates an item and places it into the priority queue			*
272             // ******************************************************************
273             void backpack::putItem(unsigned short weight, unsigned short cost){
274             	item temp_item;
275             	temp_item.setData(weight,cost,(int)(this->item_queue.size())+1);
276             	this->item_queue.push(temp_item);
277             }
278             
279             // ******************************************************************
280             // * FUNCTION : store_item_array IN : CLASS backpack				*
281             // * Dumps the Item Queue in order into an Array for Rand. Access	*
282             // ******************************************************************
283             void backpack::store_item_array(){
284             	this->item_array = new item[this->totalItems];
285 rizwank 1.1 	for ( int i = 0; this->totalItems > i; i++){
286             		this->item_array[i] = this->item_queue.top();
287             		this->item_queue.pop();
288             	}
289             }
290             
291             // ******************************************************************
292             // * FUNCTION : get_totalItems	IN : CLASS backpack					*
293             // * Returns the number of items for consideration.					*
294             // ******************************************************************
295             unsigned short backpack::get_totalItems(){
296             	return this->totalItems;
297             }
298             
299             // ******************************************************************
300             // * FUNCTION : get_maxWeight	IN : CLASS backpack					*
301             // * Returns the maximum weight for this backpack.					*
302             // ******************************************************************
303             unsigned short backpack::get_maxWeight(){
304             	return this->maxWeight;
305             }
306 rizwank 1.1 
307             // ******************************************************************
308             // * FUNCTION : get_Item		IN : CLASS backpack					*
309             // * Returns a particular item from the item array					*
310             // ******************************************************************
311             item backpack::get_Item(unsigned short index){
312             	return ( this->item_array[index] );
313             }
314             
315             // ******************************************************************
316             // * FUNCTION : branch_and_bound IN : CLASS backpack				*
317             // * Performs Best-First-Fit Branch and Bound on this backpack		*
318             // * while keeping track of the nodecounts.							*
319             // * Create a template key with the best possible bound.			*
320             // * Place that key into the queue and start a loop					*
321             // * As long as the 'onwards' flag is TRUE, repeat:					*
322             // *	Take the topmost (highest bound) key out of the queue.		*
323             // *	If that bound has all of its items processed, clear ownards	*
324             // *	Else, create two keys from the original key					*
325             // *	One without the next item and one with.						*
326             // *	Place the new keys into the queue and discard the current	*
327 rizwank 1.1 // *	Repeat														*
328             // * If the loop is ended, the top item on the queue is the best	*
329             // * possible solution for this knapsack.							*
330             // * Fetch all the information and print it out.					*
331             // ******************************************************************
332             void backpack::branch_and_bound(){
333             	key temp_key;
334             	
335             	temp_key.initKey(this);
336             	this->key_queue.push(temp_key);
337             	this->addnodeCount++;
338             
339             	bool onwards = 1;
340             
341             	do
342             	{
343             		temp_key = key_queue.top();
344             		this->key_queue.pop();
345             		if ( temp_key.doneItems() ) {
346             			onwards = 0;
347             		}
348 rizwank 1.1 		else {
349             			this->worknodeCount++;
350                         temp_key.flagNext();
351                             this->key_queue.push(temp_key);
352             				this->addnodeCount++;
353             			temp_key.addCurItem();
354             			if (temp_key.getBound() != 0){
355             				this->key_queue.push(temp_key);
356             				this->addnodeCount++;
357             			}
358             		}
359             	}
360             	while (onwards);
361             	
362             
363             
364             	printf("Case n=%2d Total possible nodes in thie state space tree is 2^%2d-1\n",this->totalItems,this->totalItems);
365             	printf("          Number of nodes placed in the priority queue: %6d\n",this->addnodeCount);
366             	printf("          Number of nodes examined/split:               %6d\n",this->worknodeCount);
367             
368             	
369 rizwank 1.1 	printf("\nObjects Chosen \n");
370             
371             	printf("          Objects      Weights      Values\n");
372             	int totalitemsinserted = 0;
373             	for (int i = 0; this->totalItems > i; i++) {
374             		if ( temp_key.checkItem(i) ) {
375             			printf("             %2d           %2d           %2d\n", this->item_array[i].getNumber(),  this->item_array[i].getWeight(), this->item_array[i].getCost());
376             			totalitemsinserted++;
377             		}
378             	}
379             	printf("======================================================\n");
380             	printf("Totals:      %2d           %2d           %2d\n",totalitemsinserted, temp_key.getWeight(),  temp_key.getValue());
381             	printf("Ratio :     %2.5f\n", ((float)temp_key.getValue()/(float)temp_key.getWeight()));
382             }
383             
384             // ******************************************************************
385             // * FUNCTION : main												*
386             // * Initalizes the backpack and the items inside.					*
387             // * Copies those items into an array, prints out the items.		*
388             // * Run the branch_and_bound method.								*
389             // ******************************************************************
390 rizwank 1.1 int main(int argc, char *argv[])
391             {
392             	item temp_item;
393             	printf("CS331_Project 4, by Rizwan Kassim.\n");
394             	printf("Version 3\n");
395             	printf("All compiled / source code are (C) Rizwan Kassim 2003\n\n");
396             
397             
398             	printf("============================ KNAPSACK ONE ================================\n");
399             	backpack knapsackOne;
400             
401 rizwank 1.2 	knapsackOne.initBackpack(25,200); // 5 total items, 17 total weight
402             knapsackOne.packitem(70,70);
403             knapsackOne.packitem(76,76);
404             knapsackOne.packitem(55,55);
405             knapsackOne.packitem(17,17);
406             knapsackOne.packitem(70,70);
407             knapsackOne.packitem(77,77);
408             knapsackOne.packitem(52,52);
409             knapsackOne.packitem(81,81);
410             knapsackOne.packitem(11,11);
411             knapsackOne.packitem(31,31);
412             knapsackOne.packitem(57,57);
413             knapsackOne.packitem(47,47);
414             knapsackOne.packitem(93,93);
415             knapsackOne.packitem(53,53);
416             knapsackOne.packitem(83,83);
417             knapsackOne.packitem(33,33);
418             knapsackOne.packitem(1,1);
419             knapsackOne.packitem(59,59);
420             knapsackOne.packitem(29,29);
421             knapsackOne.packitem(33,33);
422 rizwank 1.2 knapsackOne.packitem(78,78);
423             knapsackOne.packitem(79,79);
424             knapsackOne.packitem(37,37);
425             knapsackOne.packitem(26,26);
426             knapsackOne.packitem(83,83);
427 rizwank 1.1 	knapsackOne.store_item_array();
428             
429             	
430             	for ( int i = 0; knapsackOne.get_totalItems() > i; i++){
431             		temp_item=knapsackOne.get_Item(i);
432             		printf("Item Number %2d : %2d cost for %2d weight at ratio %2.3f\n", temp_item.getNumber(),  temp_item.getCost(), temp_item.getWeight(), temp_item.getRatio());
433             	}
434             	printf("\n");
435             
436             	knapsackOne.branch_and_bound();
437             
438             	printf("\n");
439             }
440             
441             
442             /* 
443             Modifications to the original branch-and-bound algorithim/approach
444             
445             This program was to compute the maximum value that can be fit into a bag --- Using Levitin p380 for reference
446             right now. As our problem is actually a SUBSET of the given problem ,we can simplify some of the functions.
447             We also don't want any packs too small, but we'll let this compute, see how big the state tree is versus
448 rizwank 1.1 an alternative algorithm.
449             
450             	knapsackOne.initBackpack(5,17); // 5 total items, 17 total weight
451             	knapsackOne.putItem(4,1);
452             	knapsackOne.putItem(7,1);
453             	knapsackOne.putItem(5,1);
454             	knapsackOne.putItem(9,1);
455             	knapsackOne.putItem(1,1);
456             
457             For given same, 2^5-1 possible nodes in tree, 14 nodes placed, 7 split.
458             
459             Lets try something larger. n=10 1,2,3,4,5,6,7,8,9,10 => 18
460             
461             Oooh, we can vary the max backpack item count to only use a certain amount of the items!
462             
463             Whats interesting is that we can keep the various ratio calculations, as we WOULD rather insert an item of 10 lbs rather than 1
464             We just equate weight and value later on! (Or set a fixed ratio of 1)		
465 rizwank 1.2 		knapsack insert (value,value)
466             		
467             		This was max 2^10-1 with only 47 nodes and 33 splits.
468 rizwank 1.1 		
469 rizwank 1.2 And lets try with a random set of 25 numbers!
470             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
471             
472             
473             
474             then 50:
475             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
476             
477             
478             
479 rizwank 1.1 		
480             		*/
481             

Rizwan Kassim
Powered by
ViewCVS 0.9.2