Solved

C++ -- Knapsack Problem

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

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Suggested Solutions

Iteration: Iteration is repetition of a process. A student who goes to school repeats the process of going to school everyday until graduation. We go to grocery store at least once or twice a month to buy products. We repeat this process every mont…
Calculating holidays and working days is a function that is often needed yet it is not one found within the Framework. This article presents one approach to building a working-day calculator for use in .NET.
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.

747 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

12 Experts available now in Live!

Get 1:1 Help Now