More Recursive Backtracking

CS 106B: Programming Abstractions

Spring 2023, Stanford University Computer Science Department

Lecturer: Chris Gregg, Head CA: Neel Kishnani

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
Assignment 4 will be released next Thursday (after the midterm)
The midterm is next Wednesday, 7pm-9pm, in person. See the midterm page for details.

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

A struct is a data structure in C++ that allows us to package together different types of data into one type.
- Yes, we can create new types ourselves. One way to do this is with a struct.
- We often end the name of the new type with an uppercase T (or an _t) to indicate that it is a type. In this case, we have created an "object" type, so we name it objectT.
- If you have a Python background, you might have used a dict for this concept, and you might think that a map<string, int> would be a good idea here. While it would work for this particular case, a map is generally not a good data structure here, mainly because of two reasons:
  1. It is a pretty heavyweight data structure for our purposes, which means that it is going to come with overhead (memory or reduced speed).
  2. In C++, we cannot have a map that holds different value types. A struct can have any types we want, e.g.,
    struct myNewDataT { int i; char c; string s; double d; };
- We refer to a struct member by its name using dot notation, so in the case of an objectT called objectA, we would refer to objectA.weight and objectA.value.

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);
```
- Note that we are not finding the combination of values and weights that will fill our knapsack the best – that will come later. For now, we just want the "best score," which is an int.

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 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!
    }
```
We have another base case, as well – the case where we have exhausted our objects vector, meaning that we have a legitimate solution:
```
    if (objects.isEmpty()) {
        return currentScore;
    }
```

Next, we remove the object that we are going to check

    objectT originalObject = objects.remove(objects.size() - 1);

Now we can recursively call the function without adding the object (i.e., we ignore the object and don't put it into our knapsack)
```
    int scoreWithoutObject = fillKnapsack(objects, weight, currentScore);
```

Now we include the object, but to do so we have to update our weight and score. Then we can recurse again:

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

    int scoreWithObject = fillKnapsack(objects, newWeight, newScore);

We can now replace the object ("unchoose") at the end of our loop:
```
    objects.add(originalObject);
```
And finally, we use the max function to return the best score that we have received:
```
    return max(scoreWithObject, scoreWithoutObject);
}
```

Here is the full code:

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

  if (objects.isEmpty()) {
      return currentScore;
  }

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

  // don't include the object
  int scoreWithoutObject = fillKnapsack(objects, weight, currentScore);

  // include the object
  int newWeight = weight - originalObject.weight;
  int newScore = currentScore + originalObject.value;

  int scoreWithObject = fillKnapsack(objects, newWeight, newScore);

  objects.add(originalObject);

  return max(scoreWithObject, scoreWithoutObject);
}

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

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 two parameters: a "currentSolutionObjects" Vector, and a "bestSolutionObjects" Vector:

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

We have to keep track of not only the best total solution, but we have to pass along the current solution so that we can calculate whether we have a better solution, and keep track of it throughout the recursion:

    if (objects.isEmpty()) {
        // calculate the score of the best solution
        int bestScoreSoFar = 0;
        for (objectT obj : bestSolutionObjects) {
            bestScoreSoFar += obj.value;
        }

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

The rest of the solution must keep track of the current solution to pass along:

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

      // don't include the object
      int scoreWithoutObject =
          fillKnapsack(objects, weight, currentScore, currentSolutionObjects,
                       bestSolutionObjects);

      // include the object
      int newWeight = weight - originalObject.weight;
      int newScore = currentScore + originalObject.value;

      // put the object into the current bag
      currentSolutionObjects.add(originalObject);

      int scoreWithObject =
          fillKnapsack(objects, newWeight, newScore, currentSolutionObjects,
                       bestSolutionObjects);

      // remove the object from the current solution
      currentSolutionObjects.remove(currentSolutionObjects.size() - 1);

      objects.add(originalObject);

      return max(scoreWithObject, scoreWithoutObject);
  }

Slide 9

Knapsack, find best solution, full code:

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

    if (objects.isEmpty()) {
        // calculate the score of the best solution
        int bestScoreSoFar = 0;
        for (objectT obj : bestSolutionObjects) {
            bestScoreSoFar += obj.value;
        }

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

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

    // don't include the object
    int scoreWithoutObject =
        fillKnapsack(objects, weight, currentScore, currentSolutionObjects,
                     bestSolutionObjects);

    // include the object
    int newWeight = weight - originalObject.weight;
    int newScore = currentScore + originalObject.value;

    // put the object into the current bag
    currentSolutionObjects.add(originalObject);

    int scoreWithObject =
        fillKnapsack(objects, newWeight, newScore, currentSolutionObjects,
                     bestSolutionObjects);

    // remove the object from the current solution
    currentSolutionObjects.remove(currentSolutionObjects.size() - 1);

    objects.add(originalObject);

    return max(scoreWithObject, scoreWithoutObject);
}

Slide 10

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 the object to our potential solution vector 
      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);
}