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;
}

void main() should be int main().

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.

Try looking at the Wikipedia page on the Knapsack Problem.

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);
	}