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

Threaded View

  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

Posting Permissions

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





Click Here to Expand Forum to Full Width

Featured