Cutting stock recursion

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

• Okay, and what is your question? – Emily L. Aug 28 '14 at 15:58
• @EmilyL. Just review the code in general, if there is no specific question. – 200_success Aug 28 '14 at 16:02
• What is a Vector? Is that your own special class or do you mean std::vector? – jliv902 Aug 28 '14 at 19:47
• @jliv902 yes it's a special class – Abdoelrhman Sep 1 '14 at 19:38

1 Answer

• 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.