Improve company productivity with a Business Account.Sign Up

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 3509
  • Last Modified:

C++ -- Knapsack Problem

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
ExpExchHelp
Asked:
ExpExchHelp
  • 3
1 Solution
 
ExpExchHelpAuthor Commented:
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
 
TommySzalapskiCommented:
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
 
ExpExchHelpAuthor Commented:
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
 
ExpExchHelpAuthor Commented:
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
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

Get expert help—faster!

Need expert help—fast? Use the Help Bell for personalized assistance getting answers to your important questions.

  • 3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now