Thread: Help with my Knapsack Code

  1. #1
    Registered User
    Join Date
    Nov 2006
    Posts
    2

    Help with my Knapsack Code

    I'm trying to write a breadth first search to solve the 0/1 knapsack problem and I'm not exactly sure what to do. I have a solution for a depth first search. Can anyone help me?


    Depth First Search
    Code:
    void depth_first(vector<bool> pile, double cur_weight, double cur_value)
    {
    	//if this value is better than the best value
    	if(cur_value >= best_value)
    	{
    		best_value = cur_value;
    		best_weight = cur_weight;
    		//save this solution
    		best_solution.clear();
    		vector<bool>::iterator itr = pile.begin();
    		while(itr != pile.end()){
    			best_solution.push_back(*itr++);
    		}
    	}
    	states_visited++;
    	
    	//check for a leaf
    	if(pile.size() < num_objects )
    	{
    		//check the children for 1 or 0. 1 include 0 isn't
    		double next_weight = cur_weight + weight[pile.size()];
    		double next_value = cur_value + value[pile.size()];
    
    		//if the next pile <= max_weight then check it
    		if(next_weight <= max_weight)
    		{
    			vector<bool> new_pile(pile);
    			new_pile.push_back(true);
    			depth_first(new_pile,next_weight,next_value);
    		}
    		//next piles with 0 since they won't go over weight
    		vector<bool> new_pile(pile);
    		new_pile.push_back(false);
    		depth_first(new_pile,cur_weight,cur_value);
    	}
    }

    Rest of my program
    Code:
    #include <iostream>
    #include <vector>
    #include <string>
    #include <fstream>
    #include <iomanip>
    using namespace std;
    
    #define ARRAY_SIZE 30
    
    //arrays for the weights and the corresponding values
    double weight[ARRAY_SIZE];
    double value[ARRAY_SIZE];
    
    //global variables to hold the info for the problem
    unsigned int num_objects;
    double max_weight;
    unsigned int states_visited;
    
    //global variables to hold the best solution
    double best_value;
    double best_weight;
    vector<bool> best_solution;
    
    void setup(string &filename)
    {
    	ifstream infile;
    	infile.open(filename.c_str());
    	if(!infile)
    	{
    		cout << "Error: could not open the file." << endl;;
    		exit(0);
    	}
    
    	//read in the data from the file
    	cout << "Depth-first search" << endl;
    	infile >> num_objects;
    	cout << "Number of Objects: " << num_objects << endl;
    	infile >> max_weight;
    	cout << "Maximum Weight: " << max_weight << endl;
    	for(unsigned int i=0; i<num_objects; i++)
    	{
    		//input is weight then value for each object
    		infile >> weight[i];
    		infile >> value[i];
    	}
    	infile.close();
    
    	//make sure best_solution vector is cleared
    	best_solution.clear();
    }
    
    void main()
    {
    	vector<bool> pile;
    	double cur_weight = 0.0;
    	double cur_value = 0.0;
    
    	//get the info from the file and set it up
    	string filename;
    	cout << "\nEnter knapsack filename: ";
    	cin >> filename;
    	setup(filename);
    
    	//run the search
    	depth_first(pile,cur_weight,cur_value);
    
    	//output all the info
    	cout << "\n# Piles Checked: " << states_visited-1;
    	cout << "\nBest Value: " << setprecision(10) << best_value;
    	cout << "\nBest Weight: " << setprecision(10) << best_weight;
    	cout << "\nOrder of Best Pile (indicates position in file with index=1): " << endl;
    
    	for(int i=0; i<num_objects; i++)
    	{
    		if( best_solution[i] == 1 )
    		{
    			int j = i+1;
    			cout << j << endl;
    		}
    	}
    	cout << endl;
    }

  2. #2
    MFC killed my cat! manutd's Avatar
    Join Date
    Sep 2006
    Location
    Boston, Massachusetts
    Posts
    870
    void main() should be int main().
    Silence is better than unmeaning words.
    - Pythagoras
    My blog

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Posting your attempt at breadth-first search would be a start.
    We can't say where you're going wrong without looking at your code.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #4
    MFC killed my cat! manutd's Avatar
    Join Date
    Sep 2006
    Location
    Boston, Massachusetts
    Posts
    870
    Try looking at the Wikipedia page on the Knapsack Problem.
    Silence is better than unmeaning words.
    - Pythagoras
    My blog

  5. #5
    Registered User
    Join Date
    Nov 2006
    Posts
    2
    I don't have any code yet. I'm looking for a hint about where I should start. I know that BFS requires a higher level of looping and I think the only difference in my program should be in the following part of the depth_first function:

    Code:
    	//check for a leaf
    	if(pile.size() < num_objects )
    	{
    		//check the children for 1 or 0. 1 include 0 isn't
    		double next_weight = cur_weight + weight[pile.size()];
    		double next_value = cur_value + value[pile.size()];
    
    		//if the next pile <= max_weight then check it
    		if(next_weight <= max_weight)
    		{
    			vector<bool> new_pile(pile);
    			new_pile.push_back(true);
    			depth_first(new_pile,next_weight,next_value);
    		}
    		//next piles with 0 since they won't go over weight
    		vector<bool> new_pile(pile);
    		new_pile.push_back(false);
    		depth_first(new_pile,cur_weight,cur_value);
    	}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Enforcing Machine Code Restrictions?
    By SMurf in forum Tech Board
    Replies: 21
    Last Post: 03-30-2009, 07:34 AM
  2. Values changing without reason?
    By subtled in forum C Programming
    Replies: 2
    Last Post: 04-19-2007, 10:20 AM
  3. Obfuscated Code Contest: The Results
    By Stack Overflow in forum Contests Board
    Replies: 29
    Last Post: 02-18-2005, 05:39 PM
  4. Obfuscated Code Contest
    By Stack Overflow in forum Contests Board
    Replies: 51
    Last Post: 01-21-2005, 04:17 PM
  5. Interface Question
    By smog890 in forum C Programming
    Replies: 11
    Last Post: 06-03-2002, 05:06 PM