Solved

C++ Merging a function

Posted on 2011-02-19
13
389 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 8
  • 5
13 Comments
 

Author Comment

by:ExpExchHelp
ID: 34933594
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
ID: 34934204
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
ID: 34934259
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
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 86

Expert Comment

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

Author Comment

by:ExpExchHelp
ID: 34934422
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
ID: 34934516
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
 

Author Comment

by:ExpExchHelp
ID: 34934694
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
ID: 34934895
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
ID: 34935075
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
ID: 34935112
>>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
ID: 34937142
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
ID: 34937147
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
ID: 34939177
I still welcome your feedback (comments) on how the ForLoop and WhileLoop works.
0

Featured Post

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

What is C++ STL?: STL stands for Standard Template Library and is a part of standard C++ libraries. It contains many useful data structures (containers) and algorithms, which can spare you a lot of the time. Today we will look at the STL Vector. …
This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

738 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