More Recursive Backtracking

CS 106B: Programming Abstractions

Autumn 2020, Stanford University Computer Science Department

Lecturers: Chris Gregg and Julie Zelenski

A backpack ('knapsack') that says it can hld 15kg, and a number of weights with a dollar amount and a weight. The weights are $4, 12kg; $2, 2kg; $2, 1kg; $10, 4kg, and $1, 1kg

Slide 2

Announcements

Assignment 3 is due tonight and Assignment 4 will be released tomorrow.

Slide 3

Today's Goals:

Continue exploring the idea of recursive backtracking with the "knapsack problem"

Slide 4

The Knapsack Problem: Find the best solution

A backpack ('knapsack') that says it can hld 15kg, and a number of weights with a dollar amount and a weight. The weights are $4, 12kg; $2, 2kg; $2, 1kg; $10, 4kg, and $1, 1kg

One famous problem in theoretical computer science is the so-called knapsack problem. Given a target weight and a set of objects in which each object has a value and a weight, determine a subset of objects such that the sum of their weights is less than or equal to the target weight and the sum of their values is maximized.

For this problem we will represent an object with the following struct:

struct objectT {
    int weight; // You may assume this is greater than or equal to 0
    int value;  // You may assume this is greater than or equal to 0
};

We are going to write the function:

int fillKnapsack(Vector<objectT>& objects, int targetWeight)

Our function considers all possible combinations of objectT from objects (such that the sum of their weights is less than or equal to targetWeight) and returns the maximum possible sum of object values.

Slide 5

The Knapsack Problem: Find the best solution

int fillKnapsack(Vector<objectT>& objects, int targetWeight)

Basic idea:
- Keep track of the weight and keep track of the best total value ("score").
- Loop over all items, adding value to the knapsack, and subtracting the weight of items from the total weight allowed.
- If the weight goes below zero, we have too many items.
- Must have a helper function! Our helper function:
```
int fillKnapsack(Vector<objectT>& objects, int weight, int currentScore);
```

Slide 6

The Knapsack Problem: Solution

First, we can set up our struct and call the helper function:

struct objectT {
    int weight; // You may assume this is greater than or equal to 0
    int value;  // You may assume this is greater than or equal to 0
};

int fillKnapsack(Vector<objectT>& objects, int targetWeight) {
    return fillKnapsack(objects, targetWeight, 0);
}

This is our helper function (the recursive one):

int fillKnapsack(Vector<objectT>& objects, int weight, int currentScore) {

First, we need our base cases. Remember, the weight parameter is decreasing as we add elements. So, if the weight goes below zero, you can return 0 score, because this is an invalid solution (the backpack would break):
```
    if (weight < 0) {
        return 0; // we tried too much weight!
    }
```

We do have the possibility of another base case, too – what if we have used up all of the objects (either by adding them or not adding them)?

    if (objects.isEmpty()) {
        return currentScore; // we are out of objects, so return the current score 
    }

We remove the object we are looking at so we can recurse (we need to keep track of the value and remember to "unchoose" it at the end of our loop!)
```
     objectT originalObject = objects.remove(objects.size() - 1); 
```
Now, as we have done for other problems, we need to recurse by either using the object, or not using the object (so, two recursive calls). Let's make the first recursive call a call that does not use the object. We need the score returned so we can compare it to the other case (remember, we are looking for the best score):
```
     int scoreWithoutObj = fillKnapsack(objects, weight, currentScore);     
```

In order to recurse on the case where we do want to include the object, we need updated weight and score calculations. Then we recurse:

    int newWeight = weight - originalObject.weight;
    int newCurrentScore = currentScore + originalObject.value;

    // put the object in the bag and recurse
    int scoreWithObj = fillKnapsack(objects, newWeight, newCurrentScore); 

We can now replace the object ("unchoose") at the end of our loop:
```
    objects.add(originalObject);
```
And finally, we return the local best score (the max function will return the value that is greatest):
```
    return max(scoreWithObj, scoreWithoutObj);
}
```

Here is the full code:

int fillKnapsack(Vector<objectT> &objects, int weight, int currentScore) {
  // base case 1: we tried too much weight!
  if (weight < 0) {
      return 0;
  }

  // base case 2: we are out of objects
  if (objects.isEmpty()) {
      return currentScore;
  }

  // remove object for recursion, and save
  objectT originalObject = objects.remove(objects.size() - 1);

  // do not put the object in the bag and recurse
  int scoreWithoutObj = fillKnapsack(objects, weight, currentScore);

  int newWeight = weight - originalObject.weight;
  int newCurrentScore = currentScore + originalObject.value;

  // put the object in the bag and recurse
  int scoreWithObj = fillKnapsack(objects, newWeight, newCurrentScore);

  // replace object so calling function has same state as before call
  objects.add(originalObject);

  return max(scoreWithObj, scoreWithoutObj);
}

Slide 7

Question: Why didn't we stop at the exact moment we knew the weight was too small?

Here is part of the knapsack code:

  int newWeight = weight - originalObject.weight;
  int newCurrentScore = currentScore + originalObject.value;

  // put the object in the bag and recurse
  int scoreWithObj = fillKnapsack(objects, newWeight, newCurrentScore);

We could have saved ourselves a recursive call by setting scoreWithObj to 0 after determining that newWeight was less than zero. Why didn't we do that?
This is partly a style issue, and partly an issue of "letting the base case do the work." We call this anti-pattern arms-length recursion, meaning that instead of letting the base case handle stopping the recursion, we "reach ahead" and handle it in the current case.
The reason that arms-length recursion is an anti-pattern and bad style is because it can be hard to see the logic, and it is not necessarily clear when reading through the code why it is handled there. Unless you absolutely need the speed increase, just let the recursion do its work and let the base case handle each case correctly.

Slide 8

Boggle!

Your next assignment is going to involve more recursion, and part of the assignment is going to be to write an algorithm to completely solve a game of Boggle, which has been around since 1973, and is (believe it or not) a spelling game where you have to form words from a 4 x 4 grid of letter tiles.
Your goal for that part of the assignment is going to be to recursively look at all paths in the grid to find all the words that are in a dictionary that are four letters long or longer. You can form words starting at any position in the grid, and a word is formed by traversing to any of the eight letters surrounding the letter you are currently on, not going out of bounds.

A Boggle board, with letters in a 4x4 grid. The letters in the first row of the image are 'H T D E', the second row has 'S Y R E', the third row has 'C X N A', and the fourth row has 'B U R B'

Slide 9

Back to Knapsack

What if we want to find the actual objects in the knapsack for the best solution?

Just like with partitionable, we have more work to do. We have to keep track of the best solution, which is going to be a vector of objects.

Let's start by adding on a parameter for a solutions vector, which we will pass in by reference so we can access it after the function is called:

int fillKnapsack(Vector<objectT>& objects,
                 int weight, int currentScore,
                 Vector<objectT>& bestSolutionObjects) {

Unfortunately, because of the way the decision tree works, we can't just keep modifying our best solution, because it may not be one step away from another potential best solution at any given time. In other words, we are going to need another vector, which we will call currentSolutionObjects:
```
int fillKnapsack(Vector<objectT> &objects, int weight, int currentScore,
                 Vector<objectT> &currentSolutionObjects,
                 Vector<objectT> &bestSolutionObjects) {
```

Whenever we get to a case where the number of objects in our vector is zero, we know that we have reached a potential solution. We update our bestSolutionObjects if we have indeed found a better solution:

// base case 2: we are out of objects
if (objects.isEmpty()) {
    // cout << "potential solution: " << currentSolutionObjects << endl;
    // calculate the score of best solution we have so far
    int bestScoreSoFar = 0;
    for (objectT obj : bestSolutionObjects) {
        bestScoreSoFar += obj.value;
    }

    if (currentScore > bestScoreSoFar) {
        bestSolutionObjects = currentSolutionObjects;
    }
    return currentScore;
}

We also need to add objects to our currentSolutionObjects when we put the object into the bag (and remove it after we're done):

currentSolutionObjects.add(originalObject);
int scoreWithObj =
    fillKnapsack(objects, newWeight, newBestScore, currentSolutionObjects,
                 bestSolutionObjects);
currentSolutionObjects.remove(currentSolutionObjects.size() - 1);

Slide 10

Knapsack, find best solution with the objects, full code:

int fillKnapsack(Vector<objectT> &objects, int weight, int currentScore,
                 Vector<objectT> &currentSolutionObjects,
                 Vector<objectT> &bestSolutionObjects) {
    // base case 1: we tried too much weight!
    if (weight < 0) {
        return 0;
    }

    // base case 2: we are out of objects
    if (objects.isEmpty()) {
        // cout << "potential solution: " << currentSolutionObjects << endl;
        // calculate the score of best solution we have so far
        int bestScoreSoFar = 0;
        for (objectT obj : bestSolutionObjects) {
            bestScoreSoFar += obj.value;
        }

        if (currentScore > bestScoreSoFar) {
            bestSolutionObjects = currentSolutionObjects;
        }
        return currentScore;
    }

    // remove object for recursion, and save
    objectT originalObject = objects.remove(objects.size() - 1);

    // do not put the object in the bag and recurse
    int scoreWithoutObj =
        fillKnapsack(objects, weight, currentScore, currentSolutionObjects,
                     bestSolutionObjects);

    int newWeight = weight - originalObject.weight;
    int newBestScore = currentScore + originalObject.value;

    // put the object in the bag and recurse
    currentSolutionObjects.add(originalObject);
    int scoreWithObj =
        fillKnapsack(objects, newWeight, newBestScore, currentSolutionObjects,
                     bestSolutionObjects);
    currentSolutionObjects.remove(currentSolutionObjects.size() - 1);

    // replace object so calling function has same state as before call
    objects.add(originalObject);

    if (scoreWithoutObj > scoreWithObj) {
        return scoreWithoutObj;
    } else {
        return scoreWithObj;
    }
}

Slide 11

Finding all Knapsack Solutions??

What if we wanted to find all knapsack solutions?
- We probably wouldn't. This is any solution that fits into the backpack – that could be lots and lots of solutions!
But, we could do it. We could rip out the code that bothers to check for a value, because any value would work.
We have to add a vector to hold all the solutions
Here is the code:

// find all solutions, including the objects
void findAllKnapsackSolutions(Vector<objectT> &objects, int weight,
                              Vector<objectT> &currentSolutionObjects,
                              Vector<Vector<objectT>> &allSolutions) {
    // base case 1: we tried too much weight!
    if (weight < 0) {
        // not a valid solution
        return;
    }

    // base case 2: we are out of objects
    if (objects.isEmpty()) {
        // cout << "potential solution: " << currentSolutionObjects << endl;
        allSolutions.add(currentSolutionObjects);
        return;
    }

    // remove object for recursion, and save
    objectT originalObject = objects.remove(objects.size() - 1);

    // do not put the object in the bag and recurse
    findAllKnapsackSolutions(objects, weight, currentSolutionObjects,
                             allSolutions);

    int newWeight = weight - originalObject.weight;

    // put the object in the bag and recurse
    currentSolutionObjects.add(originalObject);
    findAllKnapsackSolutions(objects, newWeight, currentSolutionObjects,
                             allSolutions);
    currentSolutionObjects.remove(currentSolutionObjects.size() - 1);

    // replace object so calling function has same state as before call
    objects.add(originalObject);
}

void findAllKnapsackSolutions(Vector<objectT> &objects, int targetWeight,
                              Vector<Vector<objectT>> &allSolutions) {
    Vector<objectT> currentSolution;
    findAllKnapsackSolutions(objects, targetWeight, currentSolution,
                             allSolutions);
}