Stock Pipe Cutting using Recursion

This problem is from the Stanford Open Course CS106B Programming Abstractions Assignment #3
Problem number 6 here.


"You are charged with buying the plumbing pipes for a construction project. Your foreman gives you
a list of the varying lengths of pipe needed. Home Depot sells stock pipe in one fixed length. You
can divide 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.


The recursive function CutStock(Vector & requests, int stockLength) is given a
vector of the lengths needed and the stock pipe length. It 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: {4,4,1} {3,7} {8} and have two small leftover remnants. There are other possible arrangements that also fit
into three stock pipes, but it cannot be done with fewer."

We are allowed to use the specified function as a wrapper function.

Here is my solution code. Is this a good way to solve the problem? Are there any other ways to do so?

```
/*
* CutStock.cpp
* ------------
* Name: Ratul Sarna
* This program accepts a list of lengths of pipes needed by the
* user and the length of the stock pipe available. It returns the minimum
* number of stock pipes required to satisfy the list of requested pipes
*/

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

void initializeRequests(Vector & requests);
int cutStock(Vector & requests, int & stockLength);
int recCutStock(Vector & reqCopy, int stockLength);

int main() {
Vector requests;
initializeRequests(requests);
int stockLength = getInteger("Enter the stock length: ");
cout & requests) {
while (true) {
int votes = getInteger("Enter required length (-1 to quit): ");
if (

Congratulations on creating a readable, well-structured, working program. That is certainly a sign that you're well on your way to mastering programming in C++. I have found a couple of things that could help you improve your code.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid.

Think carefully about signed vs. unsigned integers

We don't have the contents of the non-standard include files "simpio.h", "console.h" and "vector.h" but can infer what's likely in them. Specifically, if Vector.size() returns a signed number, all is well, but if (as with std::vector<>), Vector.size() returns and unsigned number, then each of the comparisons should probably also use an unsigned number. This suggests, for example, that your index and possibly the pipe lengths should all be unsigned unless you're contemplating the use of negative length pipes. Negative length pipes are typically not stocked by Home Depot!

Consider bounding the problem

The assignment already notes that the maximum number of pipes is simply the length of the Vector (which I'll call \$n\$), but what about the minimum? It's not difficult to see that the minimum would be $$m = \left\lceil\frac{\sum_{i=0}^{n}p_i}{l}\right\rceil$$where \$p_i\$ is the length of each pipe and \$l\$ is the standard pipe length. This suggests that once you get to this number \$m\$, the algorithm can stop because no further reduction is possible. It's an optional test, but it could be useful for very large sets.

Consider improving the algorithm

If we test this code with the sequence {9, 9, 7, 1, 1, 3} with a standard length of 10, the program correctly reports that the number of pipes is 3. However, if we rearrange the array and give it {1, 1, 7, 3, 9, 9} it reports 4. Can you see why? If so, try to alter your algorithm to calculate the correct answer no matter what the sequence.

Consider not making a copy of the vector

The cutStock routine currently makes and operates on a copy of the vector, but is that really needed? If the intent is to leave the original vector untouched, it should be declared const; otherwise simply use it without making a copy.

In all, this is a good effort. Welcome to CodeReview!

StackExchange Code Review Q#59088, answer score: 11