# Help with my Knapsack Code

• 11-23-2006
ghop2003
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; }```
• 11-24-2006
manutd
void main() should be int main().
• 11-24-2006
Salem
```        //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);         }```