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