Solved

C++ -- Knapsack Problem

Posted on 2011-02-19
4
3,392 Views
Last Modified: 2012-06-27
Hello,

I'm trying to develop code (in C++) for the "Knapsack Problem".    More information on this concept can be found at:
http://en.wikipedia.org/wiki/Knapsack_problem

For right now, I'd like to keep it simply -- so my solution is focused on the "0-1" method (i.e., select an item or don't select an item... and I don't want to have multiple items of the same kind either).

However, instead of looking at only the "weight constraint", I also would like to include a second constraint... "volume".

I've solved the optimal answer -- maximizing "value -- in MS-Excel (using Solver).    See attached XLS.

Also, I've googled for some code (for starters) and came across a potential solution in C++.   I'm not exactly certain if this sample code addresses the concept (per Wiki and my XLS).

At this time, I'm using an input file (attached) and display the items (plus their value, weight, and volume) to the console.    Each of these are stored in their respective arrays.

Does anyone have a recommendations how to accomplish this task?

Again, attached are:
1. Solution in MS-Excel
2. Current C++ code
3. Input.txt file (for C++ code)
4. Some sample code in C++.... not sure if it's method comes even close to the concept as described on Wikipedia and solved in MS-Excel.

Thanks,
EEH


Knapsack.xls
Current-C-Plus-Plus-Code.txt
input.txt
CPlusPlus.cpp
0
Comment
Question by:ExpExchHelp
  • 3
4 Comments
 

Author Comment

by:ExpExchHelp
ID: 34932954
I' slightly modified my existing C++ code.    As I'm not very familiar with pointers, can someone verify that I've applied the three pointers/arrays (in function "knapsackGreedy") correctly?

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


// Declaration section
int i, j;
int linecount = 10;
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(int* knapSack_Value, int* knapSack_Volume, int* knapSack_Weight);


// 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[i];

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

		knapsackGreedy(knapSack_Value, knapSack_Volume, knapSack_Weight);

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

void knapsackGreedy(int* knapSack_Value, int* knapSack_Volume, int* knapSack_Weight)			
{

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

}

Open in new window

0
 
LVL 37

Accepted Solution

by:
TommySzalapski earned 500 total points
ID: 34933101
The pointers aren't quite right. You are passing and declaring then just fine; however, you should be declaring them in main not in the global scope (you're passing them in to the function anyway).
Also, I would set up the 1000 as a constant.
const int ARRAY_SIZE = 1000 //or something
That way you can use it in all the functions and change it later if you want to.
i,j, and dummy should also be declared in main.
The max value and weight should be where they are, but technically should be declared as const int.

Your questions in the first post are fairly open-ended. Now that you've had some more time to work with it, do you have any more specific questions?
0
 

Author Comment

by:ExpExchHelp
ID: 34933128
TommySzalapski:

Thanks for the prompt feedback... I appreciate it.    Based on my 2nd posting -- and your response to it -- I'm not sure if I'm fully tracking all changes you recommended.  

Would you be willing to post the code w/ suggested changes?

EEH
0
 

Author Comment

by:ExpExchHelp
ID: 34933977
TommySzalapski:

I'm taking a slightly different approach now... I've posted the related question at:

http://www.experts-exchange.com/Programming/Languages/CPP/Q_26833598.html

Thoughts/recommendations?

EEH
0

Featured Post

3 Use Cases for Connected Systems

Our Dev teams are like yours. They’re continually cranking out code for new features/bugs fixes, testing, deploying, testing some more, responding to production monitoring events and more. It’s complex. So, we thought you’d like to see what’s working for us.

Question has a verified solution.

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

Okay. So what exactly is the problem here? How often have we come across situations where we need to know if two strings are 'similar' but not necessarily the same? I have, plenty of times. Until recently, I thought any functionality like that wo…
Real-time is more about the business, not the technology. In day-to-day life, to make real-time decisions like buying or investing, business needs the latest information(e.g. Gold Rate/Stock Rate). Unlike traditional days, you need not wait for a fe…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

832 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