Lecture 5/1: Backtracking 2

May 1, 2020

📂Associated files

Questions and Answers

More Recursive Backtracking

CS 106B: Programming Abstractions

Spring 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

CS106 Pixar Night is next Thursday, May 7 from 4:30-6pm. Lots more information can be found on the event page!
Assignment 3 is due tonight and Assignment 4 will be released tomorrow.
Please make sure to read Chris's Ed post regarding online privacy in CS106B and Zoom norms in our course.

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 bestScore);
```

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 bestScore) {

First, we need a base case. Remember, the weight parameter is decreasing as we add elements. So, if the weight goes below zero, you can return
```
    if (weight < 0) return 0; // we tried too much weight!
```
Next, we have to keep track of the "local" best score, because we are going to recurse down a set of paths and keep the best of the results
```
    int localBestScore = bestScore;
```

Now we can loop over all the objects, updating the local value and the weight

    int obSize = objects.size();
    for (int i = 0; i < obSize; i++) {
        objectT originalObject = objects[i];
        int currValue = bestScore + originalObject.value;
        int currWeight = weight - originalObject.weight;

We remove the object we are looking at so we can recurse (we need to remember to "unchoose" it at the end of our loop!)
```
        objects.remove(i);
```

Now we recurse, and update the result if we get a better score:

        currValue = fillKnapsack(objects, currWeight, currValue);
        if (localBestScore < currValue) {
            localBestScore = currValue);
        }

We can now replace the object ("unchoose") at the end of our loop:
```
        objects.insert(i, originalObject);
    }
```
And finally, we return the local best score:
```
    return localBestScore;
}
```

Here is the full code:

int fillKnapsack(Vector<objectT>& objects, int weight, int bestScore) {
  if (weight < 0) return 0; // we tried too much weight!
  int localBestScore = bestScore;
  int obSize = objects.size();
  for (int i = 0; i < obSize; i++) {
      objectT originalObject = objects[i];
      int currValue = bestScore + originalObject.value;
      int currWeight = weight - originalObject.weight;

      // remove object for recursion ("choose")
      objects.remove(i);

      // recurse
      currValue = fillKnapsack(objects, currWeight, currValue);
      if (localBestScore < currValue) {
          localBestScore = currValue;
      }

      // replace ("unchoose")
      objects.insert(i,originalObject);
  }
  return localBestScore;
}

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 currWeight = weight - originalObject.weight;

      // remove object for recursion
      objects.remove(i);

      // recurse
      currValue = fillKnapsack(objects, currWeight, currValue);

We could have saved ourselves a recursive call by continue-ing the loop after determining that currWeight 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 recurisvely 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, and not just any solution.
We aren't just finding a solution, we are finding the best solution, which means we have to find all the solutions, so that changes how we can progress through the solution. We can't simply remove what we added earlier, as the object we added might not be on the end any more!

Let's start by adding on a parameter for a solutions vector:

int fillKnapsack(Vector<objectT>& objects,
                 int weight, int bestScore,
                 Vector<objectT>& solutionObjects) {
  if (weight < 0) return 0; // we tried too much weight!
  int localBestScore = bestScore;
  Vector<objectT> localBestSolution = solutionObjects;
  Vector<objectT> originalSolution = solutionObjects;

We are not only keeping track of our local best solution, but we are also keeping track of our original solution to return to that case after we perform a recursion.

Now we can progress as we did before, but adding to the potential solutionObject:

 int obSize = objects.size();
  for (int i = 0; i < obSize; i++) {
      objectT originalObject = objects[i];
      int currValue = bestScore + originalObject.value;
      int currWeight = weight - originalObject.weight;

      // remove object for recursion
      objects.remove(i);

      // add it to our potential solution set
      solutionObjects.add(originalObject);

Now we recurse, and if we get a better solution, we keep track of both the value and the solution:

      // recurse
      currValue = fillKnapsack(objects, currWeight, currValue,
                               solutionObjects);
      if (localBestScore < currValue) {
          localBestScore = currValue;
          localBestSolution = solutionObjects;
      }

We can replace the object from originalObjects, but we have to completely replace our best:

      // replace
      objects.insert(i, originalObject);

      // restore solution
      solutionObjects = originalSolution;
  }

Finally, we can update our best solution, and return our best value:

  solutionObjects = localBestSolution;
  return localBestScore;
}

Slide 10

Knapsack, find best solution, full code:

int fillKnapsack(Vector<objectT>& objects,
                 int weight, int bestScore,
                 Vector<objectT>& solutionObjects) {
  if (weight < 0) return 0; // we tried too much weight!
  int localBestScore = bestScore;
  Vector<objectT> localBestSolution = solutionObjects;
  Vector<objectT> originalSolution = solutionObjects;
  int obSize = objects.size();
  for (int i = 0; i < obSize; i++) {
      objectT originalObject = objects[i];
      int currValue = bestScore + originalObject.value;
      int currWeight = weight - originalObject.weight;

      // remove object for recursion
      objects.remove(i);

      // add it to our potential solution set
      solutionObjects.add(originalObject);

      // recurse
      currValue = fillKnapsack(objects, currWeight, currValue,
                               solutionObjects);
      if (localBestScore < currValue) {
          localBestScore = currValue;
          localBestSolution = solutionObjects;
      }

      // replace
      objects.insert(i, originalObject);

      // restore solution
      solutionObjects = originalSolution;
  }
  // we now have a best solutionsObject, and a best local score
  solutionObjects = localBestSolution;
  return localBestScore;
}

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
We need to provide an empty solution – even an empty solution is a solution!

Here is the code:

// find all solutions, including the objects
void findAllKnapsackSolutions(Vector<objectT>& objects,
                 int weight,
                 Vector<objectT>& potentialSolution,
                 Vector<Vector<objectT>>& allSolutions) {
  if (weight < 0) return; // we tried too much weight!
  
  // if we made it here, we have a solution!
  allSolutions.add(potentialSolution);
  
  int obSize = objects.size();
  for (int i = 0; i < obSize; i++) {
      objectT originalObject = objects[i];
      int currWeight = weight - originalObject.weight;
  
      // remove object for recursion
      objects.remove(i);
  
      // add it to our potential solution set
      potentialSolution.add(originalObject);
  
      // recurse
      findAllKnapsackSolutions(objects, currWeight, potentialSolution, allSolutions);
      // replace
      objects.insert(i, originalObject);
  
      // remove our potential solution addition
      potentialSolution.removeBack();
  }
}
  
void findAllKnapsackSolutions(Vector<objectT>& objects,
                 int targetWeight,
                 Vector<Vector<objectT>>& allSolutions) {
    Vector<objectT> potentialSolution;
    findAllKnapsackSolutions(objects, targetWeight,
                             potentialSolution, allSolutions);
}