5 Replies - 858 Views - Last Post: 19 February 2013 - 10:25 PM Rate Topic: -----

#1 MitulP91  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 64
  • Joined: 18-July 12

Difficulty with Reading Data From File (0-1 Knapsack Problem)

Posted 19 February 2013 - 01:25 PM

Hello all,

I've been tasked with creating a brute force/exhaustive search to solve the 0-1 Knapsack problem. I have been give a sample file for input which is as follows:

3

4
5
2 1 3 2
12 10 20 15

5
6
3 2 1 4 5
25 20 15 40 50

6
10
3 2 1 5 5 6
10 10 12 10 12 12

The first number is the number of instances (3), then it follows the pattern of number of items, capacity of knapsack, weight of item, and value of item from line to line. In this code I have been told to implement the functions getInstance (reads data from the file and stores), putInstance (outputs the data to the screen), and solveInstance (analyzes the data to discover feasible subsets). The following is my current code:

#include <iostream>
#include <iomanip>
#include <fstream>
using namespace std;

// Knapsack functions ///////////////////////////////////

void getInstance (int & W, // Knapsack capacity
                  int & n, // number of items
                  int* & v, // values of items
                  int* & w) // weights of items
{
    cin >> n;
    cin >> W;
    w = new int[n];
    for (int i=0; i<n; i++) {
        cin >> w[i];
    }
    v = new int[n];
    for (int i=0; i<n; i++) {
        cin >> v[i];
    }
}

void putInstance (int W, // Knapsack capacity
                  int n, // number of items
                  int * v, // values of items
                  int * w) // weights of items
{
    cout << "There are " << n << " items." << endl;
    cout << "The knapsack capacity is " << W << "." << endl;
    
    for (int i = 0; i < n; i++) {
        cout << "\t" << i << "\t";
    }
    cout << endl;
    
    for (int i = 0; i < n; i++) {
        cout << "w: \t" << w[i] << "\t";
    }
    cout << endl;
    
    for (int i = 0; i < n; i++) {
        cout << "v: \t" << v[i] << "\t";
    }
    cout << endl;
    
    cout << "W = " << W;
}

void solveInstance (int W, // Knapsack capacity
                    int n, // number of items
                    int * v, // values of items
                    int * w) // weights of items
{    
}

int main()
{
    ifstream inFile;
    inFile.open("PA2_data.txt");
    
    if (!inFile.is_open()) {
        cerr << "Can't find input file." << endl;
        exit(1);
    }
    
    int nInsts; // number of problem instances

    cin >> nInsts;
    
    for (int i=1; i<= nInsts; i++)
    {
        int W; // Knapsack weight capacity
        int n; // Number of items
        int * v; // Values of items
        int * w; // Weights of items
        getInstance (W, n, v, w);
        
        cout << "--------------------------------\n";
        cout << "Problem instance #" <<  i << "\n";
        putInstance (W, n, v, w);
        solveInstance (W, n, v, w);
        cout << endl;
    }
    inFile.close();   
}



The program is picking up the .txt file because the error is not appearing, however the rest of the program is blank. I'm not sure why nothing from putInstance is appearing. I believe this is a problem with the file input, but I could be wrong. Any ideas?

Is This A Good Question/Topic? 0
  • +

Replies To: Difficulty with Reading Data From File (0-1 Knapsack Problem)

#2 MitulP91  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 64
  • Joined: 18-July 12

Re: Difficulty with Reading Data From File (0-1 Knapsack Problem)

Posted 19 February 2013 - 01:31 PM

** Also if you'd like any of the files (.cpp or .txt), just let me know.
Was This Post Helpful? 0
  • +
  • -

#3 jimblumberg  Icon User is online

  • member icon


Reputation: 4019
  • View blog
  • Posts: 12,407
  • Joined: 25-December 09

Re: Difficulty with Reading Data From File (0-1 Knapsack Problem)

Posted 19 February 2013 - 01:41 PM

You have several problems, first you are never reading from your file you are getting everything from the standard input (cin) not your file. Also because you are reading from the console and you don't tell the user what value they need to enter you are probably getting lost.

Jim
Was This Post Helpful? 1
  • +
  • -

#4 MitulP91  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 64
  • Joined: 18-July 12

Re: Difficulty with Reading Data From File (0-1 Knapsack Problem)

Posted 19 February 2013 - 01:41 PM

I was just testing a few things and I discovered something.

When I place a simple
cout << "hello";
before the for statement in main, the program outputs hello, but when I place it after the end of the for statement nothing appears. Seems the issue is rooted in the for statement somewhere.
Was This Post Helpful? 0
  • +
  • -

#5 MitulP91  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 64
  • Joined: 18-July 12

Re: Difficulty with Reading Data From File (0-1 Knapsack Problem)

Posted 19 February 2013 - 01:52 PM

View Postjimblumberg, on 19 February 2013 - 01:41 PM, said:

You have several problems, first you are never reading from your file you are getting everything from the standard input (cin) not your file. Also because you are reading from the console and you don't tell the user what value they need to enter you are probably getting lost.

Jim


Hello Jim,

Such a stupid mistake. I appreciate the help and thanks for your time.

Mitul
Was This Post Helpful? 0
  • +
  • -

#6 #define  Icon User is offline

  • Duke of Err
  • member icon

Reputation: 1330
  • View blog
  • Posts: 4,561
  • Joined: 19-February 09

Re: Difficulty with Reading Data From File (0-1 Knapsack Problem)

Posted 19 February 2013 - 10:25 PM

View PostMitulP91, on 20 February 2013 - 12:41 AM, said:

Hello all,

I've created a program that reads data off of a file and stores the variables for number of items, weight of items, value of items, and capacity of the knapsack. I am having difficulty finding a way to obtain all subsets of the items and analyzing them.

For example one of the given sets is as follows:

number of items (n) = 4
capacity (W) = 5
weight (w): 2 1 3 2
value: (v) 12 10 20 15

Thus I would need to find all subsets of {0,1,2,3} since there are 4 items. I've been looking around for a way to do this, but can not seem to figure it out myself.

If anyone could point me to a tutorial or help me in the right direction it would be much appreciated.

If you want to see my code, please ask.



You could use a bit for each N, 1 for included and 0 for not. A bitset would be a helpful container.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1