Cutting stock recursion

Question

This problem is identical to the one here:

Suppose that you have been assigned the job of buying the plumbing pipes for a construction project. Your foreman gives you a list of the varying lengths of pipe needed, but the distributor sells stock pipe only in one fixed size. You can, however, cut each stock pipe in any way needed. Your job is to figure out the minimum number of stock pipes required to satisfy the list of requests, thereby saving money and minimizing waste.

Your job is to write a recursive function

int cutStock(Vector<int> & requests, int stockLength);

that takes two arguments—a vector of the lengths needed and the length of stock pipe that the distributor sells—and returns the minimum number of stock pipes needed to service all requests in the vector. For example, if the vector contains [ 4, 3, 4, 1, 7, 8 ] and the stock pipe length is 10, you can purchase three stock pipes and divide them as follows:

Pipe 1: 4, 4, 1

Pipe 2: 3, 7

Pipe 3: 8

Doing so leaves you with two small remnants left over. There are other possible arrangements that also fit into three stock pipes, but it cannot be done with fewer.

/*
 * File: StockCutting.cpp
 * ----------------------
 * Name: abdulrhman eaita
 * This code minimize the needed stock for a diffrent length requests
 *
 */

#include <iostream>
#include "console.h"
#include "vector.h"
#include "simpio.h"
using namespace std;

/* Function prototypes */

int cutStock(Vector<int> & requests, int stockLength);
void bibesCutter(Vector<int> & requests, int stockLength, int &rest, int &bibes);
/* Main program */

int main() {
   Vector<int> requests;
   while (true) {
       while (true) {
           int x = getInteger("enter your requests, 0 to end: ");
           if(x == 0) break;
           requests.add(x);
       }
       int stoclLen = getInteger("Stock length?: ");
       cout << "Minimum number of stock pipes: " << cutStock(requests, stoclLen) << endl;
       requests.clear();
   }
   return 0;
}

/*
 * Function: cutStock
 * Usage: int units = cutStock(requests, stockLength);
 * ---------------------------------------------------
 * wrapper function for bibesCutter();
 */

int cutStock(Vector<int> & requests, int stockLength) {
    int bibes = 0;
    int rest = 0;
    bibesCutter(requests,stockLength, rest, bibes);
    return bibes;
}
/*
 * Function: bibesCutter
 * USage: bibesCutter(requests, stocklen, rest, bibes);
 * ----------------------------------------------------
 * Computes the minimum number of stock pipes required to satisfy
 * the vector of requests of individual pieces.
 */
void bibesCutter(Vector<int> & requests, int stockLength, int & rest, int & bibes){
    if (requests.size() == 1) {
        if (requests[0] > rest) {
            bibes++;

            //creating new rest as it's new stock and substracting the request after adding new bibe
            rest = stockLength - requests[0];

            return;
        }else{
            // substracting the request from current rest only.
            rest -= requests[0];
            return;
        }
    }else{
        Vector<int> tmp ;
        int toCheck = 0;
        // checking if there's a smaller value to remove first
        for (int i = 0; i < requests.size(); ++i) {
            if (requests[i] < rest) {
                toCheck = i;
            }
        }
        // removing first item by default, if there's no smaller cut. 
        tmp += requests[toCheck];
        requests.remove(toCheck);
        bibesCutter(tmp, stockLength, rest, bibes);
        bibesCutter(requests, stockLength, rest, bibes);
        return;
    }
}

Answer 1

• void function

  The bibesCutter itself doesn't care how many bibes have been claimed already. It only calculates how many are needed for the remaining requests. Therefore I'd recommend to change its signature to

  int bibesCutter(Vector<int> & requests, int stockLength, int & rest)
  

• Recursion

  The first recursive call to bibesCutter always falls into a base case (tmp has exactly 1 element). I suppose it is much cleaner to deal with it inline. At least you'd spare creating and destroying a vector.

  Once this is done' you'd notice that a code becomes tail recursive, so the recursion could be eliminated at all.

• Correctness

  It would be nice to prove that the algorithm yields the optimal solution. The request to fulfill with the remaining piece of pipe (toCheck) is selected pretty much at random. That, along with the above observation on recursion elimination, is a red flag.

• Misc

  tmp and toCheck are not best identifiers.

  stoclLen is a very funny typo.