Solved

C++ -- Knapsack Problem

Posted on 2011-02-19
4
3,415 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
[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
  • 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

[Webinar] Code, Load, and Grow

Managing multiple websites, servers, applications, and security on a daily basis? Join us for a webinar on May 25th to learn how to simplify administration and management of virtual hosts for IT admins, create a secure environment, and deploy code more effectively and frequently.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
C# LINQ 5 44
c# deserialize JSON from web service using JsonConvert 9 59
MFC COM Server not showing  form 4 25
using interface in TLB 3 30
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…
Article by: Nadia
Suppose you use Uber application as a rider and you request a ride to go from one place to another. Your driver just arrived at the parking lot of your place. The only thing you know about the ride is the license plate number. How do you find your U…
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 be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

739 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