please help with knapsack program
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 3 of 3

Thread: please help with knapsack program

  1. #1
    Join Date
    Aug 2007
    Posts
    28

    Question please help with knapsack program

    hello everyone, i am new to c++ and programming overall...just decided to try some things out..
    i am currently trying to implement the knapsack problem....
    this code works correctly no problem... but can someone please help me to rewrite this code so that ifstream.open would be used to read .txt file...

    the problem states:
    you can contain 10 kilograms in the knapsack, have three possible items, with weight/values of (6,700), (5,500), and (5, 400), the optimal answer would be to take the second and third items (index 1 and 2), getting a total value of 900

    the .txt input should look like this:
    10
    3
    6 700
    5 500
    5 400

    here's my code:

    Code:
    #include <iostream>
    #include <fstream>
    #include <iomanip>
    using namespace std;
    
    #define MAXN 500    /* max items*/
    #define MAXM 500  /* max capacity */
    
    char set[MAXM][MAXN];
    /* set[i][j]==1 means that for capacity i an optimal solution contains item j */
    
    unsigned int Fn[MAXM]; /* objective function */
    
    /* items */
    /*                No.      1   2   3   4   5   6   7  8    */ 
    unsigned int m[MAXN] = {6, 5, 5}; /* volume */
    unsigned int c[MAXN] = {700,  500,  400}; /* price */
    
    unsigned int M = 70; /* actual capacity */
    unsigned int N = 8;  /* number of items */
    
    void calculate()
    { 
    	unsigned int maxValue, maxIndex, i, j;
    	memset(set, 0, sizeof(set));       /* set[i][j] = 0 */
    	
    	for (i=1; i<=M; i++)
    	{ 
    		maxValue = maxIndex = 0;
    		for (j=1; j<=N; j++)              /* try the item j */
    			if (m[j]<=i && !set[i-m[j]][j])
    				if (c[j] + Fn[i-m[j]] > maxValue)
    				{  
    					maxValue = c[j] + Fn[i-m[j]];
    					maxIndex = j;
    				}
    				if (maxIndex > 0)                  /* succesful ! */
    				{
    					Fn[i] = maxValue;
    					memcpy(set[i], set[i-m[maxIndex]], N);
    					set[i][maxIndex] = 1;
    				}
    				if (Fn[i] < Fn[i-1])
    				{
    					Fn[i] = Fn[i-1];
    					memcpy(set[i], set[i-1], N);
    				}
    	}
    }
    
    void write()
    {
    	 cout << Fn[M] << endl;
    	 for (int i=1; i<=N; i++)
    		 if (set[M][i]) 
    			 cout << i << endl;
    }     
    
    int main()
    { 
      calculate();
      write();
      return 0;
    }

    i don't understand how to properly use the fstream so that it would correctly communicate with the functions and variable above

    please help me to rewrite this program by adding ifstream in it

    thank you
    Last edited by eidalina20; October 8th, 2007 at 08:08 PM. Reason: needed to put code into [code] tags

  2. #2
    Join Date
    Aug 2007
    Posts
    78

    Re: please help with knapsack program

    Put your code in code tags, see faq on how to do this. (pls edit your post so ppl have an easier job reading your code).

    You dont really state what the problem is, do you expect someone to code up the desired function?
    You already know that you can use ifstream to open a file. So do that. Or explain what exactly it is, you have problems with.

  3. #3
    Join Date
    Aug 2007
    Posts
    78

    Re: please help with knapsack program

    Quote Originally Posted by eidalina20
    i don't understand how to properly use the fstream so that it would correctly communicate with the functions and variable above
    Why dont you try coding up the function? You can use this tutorial: http://www.cplusplus.com/doc/tutorial/files.html

    The tactic i would use is: Read a line from the file into a string, make a stringstream of that string, then use that to convert the values in each line into your int values.
    See here how to use a stringstream:
    http://www.java2s.com/Tutorial/Cpp/0...ingstreams.htm

    Btw: dont use unsigned ints to indicate the value cant be negative. You can still assign a negative value, and it will give undesired results.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center