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