Assignment:

Write a program that uses backtracking recursion to solve the following problem. The inputs are: 1) the weight capacity of a boat; 2) the number of valuable item types; and 3) the weight and value of every item type. The program should find a solution that fills the boat with selected valuable items such that the total value of the items in the boat is maximized while the total weight of the items stays within the weight capacity of the boat.

The user should be allowed to enter the input in the following order. Assuming all numbers are integers.

The weight capacity of the boat

The number of valuable item types

The weight and value of each item type

Example:

Suppose the user enters the following inputs.

The weight capacity of the boat = 17

The number of valuable item types = 3

Item type 1: weight = 3, value = 7

Item type 2: weight = 6, value = 13

Item type 3: weight = 7, value = 15

Based on the above user input, your program should find the solution to be 1 Item 1 and 2 Item 3, in which the total value is 37 and the total weight is 17.

Requirements:

Your program must use the backtracking template (solve_from) discussed in class, which is given as follows.

solve_from (Queens configuration) {

if configuration already contains eight queens

Print configuration

else {

for every square p that is unguarded by configuration {

add a queen on square p to configuration;

solve_from(configuration);

remove the queen from square p of configuration;

}

}

}

Note: Programs that do not use the above template will receive 0 point.

Use C++ language for implementation

Your implementation should find a solution for small input numbers within a reasonable time period.

The program should output the solution using the format below

The solution contains:

1 Item 1

2 Item 3

Total weight: 1 * 3 + 2 * 7 = 17

Total value: 1 * 7 + 2 * 15 = 37

Tip:

You should consider a solution has been found when you can no longer add any additional item to the boat. This means that, when a solution has been found, the total weight of the items may be lower than the weight capacity of the boat. However, you cannot add any more item onto the boat.

Here is my code so far, but I'm having trouble with the initial structure and the helper functions in the Boat.h file.

//Main Function #include #include "Boat.h" #include "main.h" using namespace std;

void solve_from(Boat &Boat_Config, int itemWeights[], int itemValues[]){

cout << "Entered solve_from" << endl;

/* if(Boat_Config.is_solved()){ Boat_Config.print(number_of_items); return true; } else{ for(int i = 0; i < number_of_items; i++){ if(!Boat_Config.over_capacity()){ boat_details Item; Item.item_value = itemValues[i]; Item.item_weight = itemWeight[i]; Item.item_number = i + 1; Boat_Config.insert(Item);

//Unsure if this works----- bool victory = solve_from(Boat_Config,itemWeights[i+1],itemValues[i+1]); //-------

Boat_Config.remove(); if(victory){ return true; }

}

} return false; } */ }

int main(){

int weight_capacity,number_of_items;

//User input cout << "What is the weight capacity of the boat? : "; cin >> weight_capacity; cout << endl; cout << "How many items are there? : "; cin >> number_of_items; cout << endl;

if(number_of_items < 0){ cout << "The number of items must be greater than 0" << endl; } else{

int itemWeights[number_of_items]; int itemValues[number_of_items];

for(int i = 0, x = 1; i > itemWeights[i]; cout << endl; cout << "What is the value of Item " << x << ": "; cin >> itemValues[i]; cout << endl; } //End of User Input

Boat Boat_Configuration(number_of_items); /* bool victory = solve_from(Boat_Config); if(!victory){ cout << "No Solution Found." << endl; } */ } }

//Boat.h

const int MAX_ITEMS = 5;

class Boat{ public: Boat(int size); bool is_solved() const; bool over_capacity(int weight); void print() const; void insert(int weight); void remove(int weight); int number_of_items; int weight_capacity; int current_weight; private: int count;

};

//main.h that includes the struct for a boat

struct boat_details{ int item_weight; int item_value; int item_number; int item_count; };