Solved

C++ Merging a function

Posted on 2011-02-19
13
373 Views
Last Modified: 2012-06-27
I'm trying to develop some code for a "0-1 Knapsack" problem.     Please see also related question:
http://www.experts-exchange.com/Programming/Languages/CPP/Q_26833386.html

I realize that above posting might be too broad, so I'll attempt to break it into sub-problems.

Right now, I've built a small program that can read an external file with values (per line) equal to:  "Value", "Weight", and "Volume".    This C++ code is attached (see "Code_Current.txt").    The same file (change .txt to .cpp) uses as input file "input.txt" (also attached).

To solve the knapsack problem, I've googled for existing code and came across a program that MIGHT provide a foundation.    The code I found is attached ("Code_Google.tx".... also change .txt to .cpp).

Now, here's what I need some help with.   I'd like to integrate the function from "Code_Google" merged/integrated into my code (as I'm actually reading the input file... vs. using hard-coded values in the program).  

As I'm a C++ beginner, I'm having trouble w/ the merging (i.e. make the program flow into mine which reads the input file).

Can anyone provide me some help as to what must be changed in my program so that I can used the knapsack function?

Thanks,
EEH






Code-Current.txt
input.txt
Code-Google.txt
0
Comment
Question by:ExpExchHelp
  • 8
  • 5
13 Comments
 

Author Comment

by:ExpExchHelp
Comment Utility
Here's what I currently have....

I'm getting a bunch of compiling errors... can anyone help?!
// Required C++ libraries and header files
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <math.h>                                                                                    
#include <limits.h>
using namespace std;

#define MAXWEIGHT 800
int linecount = 10;


// Declaration section
int i, j;

int knapSack_Value[1000];
int knapSack_Volume[1000];
int knapSack_Weight[1000];
int knapSack_Max_Volume = 800;
int knapSack_Max_Weight = 900;
char dummy;

// Declarations of independent functions
void knapsackGreedy();


// Main() is the programs' "entry point"
int main()
{
        // Build object for using the input file
        ifstream myFile;                                                                             
        myFile.open("input.txt");


        // If file does not exist, feedback is output to console window
        if(!myFile.is_open()){
                cout << "File 'input.txt' not found!" << endl << endl;
                system("PAUSE");
                exit(EXIT_FAILURE);
        }


        // File data is output to the console window (including the array reference)
        cout << "Step 1: The available knapsack items are as follows:" << endl;
        cout << "====================================================" << endl << endl;
		cout << "        Value  Volume  Weight" << endl;
		
        for (i=0; i<linecount; i++){                                                                 
                // Read first integer from file (read to next non-numeric character... a ";" in this assignment)
                myFile >> knapSack_Value[i]; 
                
				// Read next character (first ";")
                myFile >> dummy;
                
				// Read second integer from file (stops at ";")
               /myFile >> knapSack_Volume[i];
                
				// Read next character (second ";")
                myFile >> dummy;
                
				// Read last integer from file (then reads next line)
                myFile >> knapSack_Weight[j];

				// Console output
				cout << "&[" << i << "] ="
                        << setw (5) << knapSack_Value[i]  << " "
                        << setw (6) << knapSack_Volume[i]  << " "
                        << setw (7) << knapSack_Weight[j]
                        << endl;
  
        }
        cout << endl << endl << endl;
	

		// Function call
		knapsackGreedy();
				
        // Pause the window console screen
        system("PAUSE");
        return 0;
}

void knapsackGreedy()			
{

	/*cout << "Testing Function call" << endl << endl << endl << endl;*/


	int a[MAXWEIGHT];														/* a[i] holds the maximum value that can be obtained using at most i weight */
	int lastAddedItem[MAXWEIGHT];											/* I use this to calculate which objects were added */
	int i, j;
	int aux;


	int value = knapSack_Value[i];
	int weight = knapSack_Weight[i];




	for (i = 0; i <= knapSack_Max_Weight; ++i) {
		a[i] = 0;
		lastAddedItem[i] = -1;
	}

	a[0] = 0;
	for (i = 1; i <= knapSack_Max_Weight; ++i)
		for (j = 0; j < linecount; ++j)
			if ((weight[j] <= i) && (a[i] < a[i - weight[j]] + value[j])) {
				a[i] = a[i - weight[j]] + value[j];
				lastAddedItem[i] = j;
			}

	aux = knapSack_Max_Weight;
	while ((aux > 0) && (lastAddedItem[aux] != -1)) {
		printf("Added object %d (%d$ %dKg). Space left: %d\n", lastAddedItem[aux] + 1, value[lastAddedItem[aux]], weight[lastAddedItem[aux]], aux - weight[lastAddedItem[aux]]);
		aux -= weight[lastAddedItem[aux]];
	}

	printf("Total value added: %d$\n", a[knapSack_Max_Weight]);

}

Open in new window

0
 
LVL 86

Expert Comment

by:jkr
Comment Utility
The following should fix your compile errors, please check the commented lines:
// Required C++ libraries and header files
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <math.h>                                                                                    
#include <limits.h>
using namespace std;

#define MAXWEIGHT 800
int linecount = 10;


// Declaration section
int i, j;

int knapSack_Value[1000];
int knapSack_Volume[1000];
int knapSack_Weight[1000];
int knapSack_Max_Volume = 800;
int knapSack_Max_Weight = 900;
char dummy;

// Declarations of independent functions
void knapsackGreedy();


// Main() is the programs' "entry point"
int main()
{
        // Build object for using the input file
        ifstream myFile;                                                                             
        myFile.open("input.txt");


        // If file does not exist, feedback is output to console window
        if(!myFile.is_open()){
                cout << "File 'input.txt' not found!" << endl << endl;
                system("PAUSE");
                exit(EXIT_FAILURE);
        }


        // File data is output to the console window (including the array reference)
        cout << "Step 1: The available knapsack items are as follows:" << endl;
        cout << "====================================================" << endl << endl;
		cout << "        Value  Volume  Weight" << endl;
		
        for (i=0; i<linecount; i++){                                                                 
                // Read first integer from file (read to next non-numeric character... a ";" in this assignment)
                myFile >> knapSack_Value[i]; 
                
				// Read next character (first ";")
                myFile >> dummy;
                
				// Read second integer from file (stops at ";")
                myFile >> knapSack_Volume[i]; // no '/' at the beginning of the line
                
				// Read next character (second ";")
                myFile >> dummy;
                
				// Read last integer from file (then reads next line)
                myFile >> knapSack_Weight[j];

				// Console output
				cout << "&[" << i << "] ="
                        << setw (5) << knapSack_Value[i]  << " "
                        << setw (6) << knapSack_Volume[i]  << " "
                        << setw (7) << knapSack_Weight[j]
                        << endl;
  
        }
        cout << endl << endl << endl;
	

		// Function call
		knapsackGreedy();
				
        // Pause the window console screen
        system("PAUSE");
        return 0;
}

void knapsackGreedy()			
{

	/*cout << "Testing Function call" << endl << endl << endl << endl;*/


	int a[MAXWEIGHT];														/* a[i] holds the maximum value that can be obtained using at most i weight */
	int lastAddedItem[MAXWEIGHT];											/* I use this to calculate which objects were added */
	int i, j;
	int aux;


	int value[1000]; // needs to be an array - and that part is incorrect -> = knapSack_Value[i];
	int weight[1000]; // needs to be an array - and that part is incorrect = knapSack_Weight[i];

        // copy the whole arrays
        memcpy(value,knapSack_Value,1000 * sizeof(int));
        memcpy(weight,knapSack_Weight,1000 * sizeof(int));


	for (i = 0; i <= knapSack_Max_Weight; ++i) {
		a[i] = 0;
		lastAddedItem[i] = -1;
	}

	a[0] = 0;
	for (i = 1; i <= knapSack_Max_Weight; ++i)
		for (j = 0; j < linecount; ++j)
			if ((weight[j] <= i) && (a[i] < a[i - weight[j]] + value[j])) {
				a[i] = a[i - weight[j]] + value[j];
				lastAddedItem[i] = j;
			}

	aux = knapSack_Max_Weight;
	while ((aux > 0) && (lastAddedItem[aux] != -1)) {
		printf("Added object %d (%d$ %dKg). Space left: %d\n", lastAddedItem[aux] + 1, value[lastAddedItem[aux]], weight[lastAddedItem[aux]], aux - weight[lastAddedItem[aux]]);
		aux -= weight[lastAddedItem[aux]];
	}

	printf("Total value added: %d$\n", a[knapSack_Max_Weight]);

}

Open in new window

0
 

Author Comment

by:ExpExchHelp
Comment Utility
jkr:

It did... thanks for the help!!

Once I run the program now, I in an endless loop.     Do you have a recommendations as to how I can modify the code so that I do the following:

- keep on adding items to the "knapsack" (greatest contributing value)
- remove that item from the available list
- ensure that I don't violate the weight constraint (max weight <= 800 units)
- ensure that I don't violate the volume constraint (max volume <= 900 units)

At this time, I'm not concerned that I'm only picking the items that contribute the greatest value (while also having a greater weight/volume).    I'm simply want to achieve the "greedy algorithm" first.

Any suggestions?

EEH
0
 
LVL 86

Expert Comment

by:jkr
Comment Utility
Well, 'endless loop' and 'input file' kinda exclude each other, don't they?
0
 

Author Comment

by:ExpExchHelp
Comment Utility
jkr:

Hmh... kinda... still, were you able to run it?   If yes, what am I missing?    Right now, it doesn't seem to work for me.  

Recommendations?

EEH
0
 
LVL 86

Expert Comment

by:jkr
Comment Utility
Well, in order to run a loop, you must have dynamic input data (e.g. provided by a user) and not static data in a file. I didn't analyze to code tht deep, but the optimizer function's concept is to work on such a - static - input array. I am afraid this would mean a *major* rewrite...
0
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 

Author Comment

by:ExpExchHelp
Comment Utility
jkr:

Ok... I'm not sure if I want to do a major rewrite.    Ok, I'm trying to use the existing code and modify for my task.    The code below executes and computes values.    

There are a few things that I don't understand or would like to change.    Could you pls provide me some help on figuring these out?

1. The code uses >> #define MAXWEIGHT 800 << as well as << int knapSack_Max_Weight = 800; <<

Can I get rid of one... if yes, which one... and what's the impact on the code?     The only thing I need to keep in mind that there will be a "maximum weight of the knapsack itself... and then there will be a max weight of all the selected items.


2.  I'm not following the flow of the next four lines.  
      aux = knapSack_Max_Weight;
      while ((aux > 0) && (lastAddedItem[aux] != -1)) {
            printf("Added object %d (%d$ %dKg). Space left: %d\n", lastAddedItem[aux] + 1, value[lastAddedItem[aux]], weight[lastAddedItem[aux]], aux - weight[lastAddedItem[aux]]);
            aux -= weight[lastAddedItem[aux]];

I'd like to rewrite this into C++ code (vs. C code).   How would I go about it?


3.   The last printf (again C code vs. C++ code) doesn't make sense to me.
printf("Total value added: %d$\n", a[knapSack_Max_Weight]);

Looking at the values that will be computed, the output equals to the sum of the "item values".   However, the line include [knapsack_Max_Weight]... why not [knapsack_Max_Value]?


Any help w/ this is truly appreciate.... I'm really pulling my hair out and don't make any progress.

Again, thousand thanks in advance.

EEH
      }






// Required C++ libraries and header files
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <math.h>                                                                                    
#include <limits.h>
using namespace std;

#define MAXWEIGHT 800

int linecount   = 10;														// The number of objects 
int value[10]  = {150, 250, 450, 150, 50, 350, 175, 275, 275, 575};			// Item's value
int volume[10] = {100, 200, 200, 200, 200, 200, 200, 200, 300, 300};		// Item's volume
int weight[10] = {100, 200, 200, 200, 200, 200, 200, 200, 400, 400};		// Item's weight
int knapSack_Max_Weight = 800;												// Maximum weight 


// Declarations of independent functions
void knapsackGreedy();


int main()
{	
	
	// Function call
	knapsackGreedy();

	// Pause the window console screen
    system("PAUSE");
    return 0;

}


void knapsackGreedy() {
	int a[MAXWEIGHT];						// a[i] holds the maximum value that can be obtained using at most i weight 
	int lastAddedItem[MAXWEIGHT];			// Calculate which objects were added
	int i, j;
	int aux;

	for (i = 0; i <= knapSack_Max_Weight; ++i) {
		a[i] = 0;
		lastAddedItem[i] = -1;
	}

	a[0] = 0;
	for (i = 1; i <= knapSack_Max_Weight; ++i)
		for (j = 0; j < linecount; ++j)
			if ((weight[j] <= i) && (a[i] < a[i - weight[j]] + value[j])) {
				a[i] = a[i - weight[j]] + value[j];
				lastAddedItem[i] = j;
			}

	aux = knapSack_Max_Weight;
	while ((aux > 0) && (lastAddedItem[aux] != -1)) {
		printf("Added object %d (%d$ %dKg). Space left: %d\n", lastAddedItem[aux] + 1, value[lastAddedItem[aux]], weight[lastAddedItem[aux]], aux - weight[lastAddedItem[aux]]);
		aux -= weight[lastAddedItem[aux]];
	}

	printf("Total value added: %d$\n", a[knapSack_Max_Weight]);

}

Open in new window

0
 
LVL 86

Accepted Solution

by:
jkr earned 500 total points
Comment Utility
1) you should keep 'MAXWEIGHT' and drop the other, since you need that constant for the array sizes.

2) you could rewrite that as

std::cout << "Added object " << lastAddedItem[aux] + 1 << "(" << value[lastAddedItem[aux]] << "$" << weight[lastAddedItem[aux]] <<"Kg" << "Space left: " << aux - weight[lastAddedItem[aux]]) << std::endl;
            aux -= weight[lastAddedItem[aux]];

3) well, all I can say is that if the result is correct, the author was right ;o)
0
 

Author Comment

by:ExpExchHelp
Comment Utility
Quick follow-up:

Once I delete >> knapSack_Max_Weight <<, won't this cause a problem in the ForLoops?

I also don't understand (as mentioned before) how it is outputting "value" when the printf statement includes "weight".

printf("Total value added: %d$\n", a[knapSack_Max_Weight]);

I'm sure I'll close this thread soon and reopen a new one... I just need to better understand the author's approach... Right now, I'm not entirely following how the program works.

EEH


0
 
LVL 86

Assisted Solution

by:jkr
jkr earned 500 total points
Comment Utility
>>Once I delete >> knapSack_Max_Weight <<, won't this cause a problem in
>>the ForLoops?

No, don't delete it - replace it with MAXWEIGHT

>>I also don't understand (as mentioned before) how it is outputting "value"
>>when the printf statement includes "weight".

Look again, it is outputting

a[knapSack_Max_Weight]

where 'knapSack_Max_Weight' is an index into an array that is created from entries of 'value[]'.
0
 

Author Comment

by:ExpExchHelp
Comment Utility
jkr:

FINAL TWO questions/comments before I close this thread:

1. Right now, item #3 is added several times.  Given that I want to create a "0-1 Knapsack" solution (once an item has been added, it CANNOT be added a 2nd time), what code needs to be added to meet remove an item from the list once it has been added to the knapsack?

2.  Is there a chance you could "walk me through" the two 2nd ForLoop and WhileLoop by adding a few comments.   As I don't fully understand what's going on in these two computations, it's tough for me to make modifications.

I assure you... I'll close this thread afterward and reopen a new related question afterwards.

Again, thousand thanks in advance!!!!

EEH

0
 

Author Comment

by:ExpExchHelp
Comment Utility
Please see previous.    'Forgot to include the latest code version.
// Required C++ libraries and header files
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <math.h>                                                                                    
#include <limits.h>
using namespace std;

int linecount = 10;															// The number of objects 
#define MAXWEIGHT 900
int knapSack_Max_Weight = 900;

int knapSack_Max_Volume = 800;
														
int itemValue[10]  = {150, 250, 450, 150, 50, 350, 175, 275, 275, 575};			// Item's itemValue
int itemVolume[10] = {100, 200, 200, 200, 200, 200, 200, 200, 300, 300};		// Item's itemVolume
int itemWeight[10] = {100, 200, 200, 200, 200, 200, 200, 200, 400, 400};		// Item's itemWeight

// Declarations of independent functions
void knapsackGreedy();


int main()
{		
	// Function call
	knapsackGreedy();

	// Pause the window console screen
    system("PAUSE");
    return 0;
}


void knapsackGreedy() {
	int a[MAXWEIGHT];						// a[i] holds the maximum itemValue that can be obtained using at most i itemWeight 
	int lastAddedItem[MAXWEIGHT];			// Calculate which objects were added
	int i, j;
	int aux;

	for (i=0; i<=knapSack_Max_Weight; ++i) {
		a[i] = 0;
		lastAddedItem[i] = -1;
	}

	a[0] = 0;
	for (i=1; i<=knapSack_Max_Weight; ++i)
		for (j=0; j<linecount; ++j)
			if ((itemWeight[j] <= i) && (a[i] < a[i - itemWeight[j]] + itemValue[j])) {
				a[i] = a[i - itemWeight[j]] + itemValue[j];
				lastAddedItem[i] = j;
			}

	aux = knapSack_Max_Weight;
	while ((aux > 0) && (lastAddedItem[aux] != -1)) {
		std::cout << "Added item# " << lastAddedItem[aux] + 1 << " (" << itemValue[lastAddedItem[aux]] << " value units; " << itemWeight[lastAddedItem[aux]] <<" weight units). " << " Weight capacity left: " << aux - itemWeight[lastAddedItem[aux]] << std::endl;
        aux -= itemWeight[lastAddedItem[aux]];
		cout << endl;
	}
	
	std::cout << "Total value of items are: " << a[knapSack_Max_Weight] << std::endl;
	cout << endl << endl;
}

Open in new window

0
 

Author Closing Comment

by:ExpExchHelp
Comment Utility
I still welcome your feedback (comments) on how the ForLoop and WhileLoop works.
0

Featured Post

Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

Join & Write a Comment

Errors will happen. It is a fact of life for the programmer. How and when errors are detected have a great impact on quality and cost of a product. It is better to detect errors at compile time, when possible and practical. Errors that make their wa…
IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

743 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

15 Experts available now in Live!

Get 1:1 Help Now