Filling Bookcase Shelves

Approach 1- Recursive

The brute force approach for the problem will be to try every possible arrangement of books and find the MINIMUM_HEIGHT. So for each book, we have two choices either to place it on the next shelf or to adjust it to the same current shelf.

The choice diagram for recursion would look something like this.

Let’s define the Function solver()parameters and how they would work.

Parameters 

1. BOOKS - Vector of Books.
2. SHELF_WIDTH -  Maximum shelf width.
3. INDEX - Index of the current book.
4. CURRENT_WIDTH - Width of all the books on a current shelf together.
5. SHELF_HEIGHT - Height of the current shelf.
6. HEIGHT - The total height of the shelf after placing the index book.

Algorithm

• We’ll check if we have traversed all books, i.e., i == BOOKS.size(), then return ‘HEIGHT’.
• Next, we add the width of ‘BOOK[INDEX]’ to the ‘CURRENT_WIDTH’.
• If this width is less than equal to ‘SHELF_WIDTH’, we have two choices either to keep the book on the same shelf or the next shelf. So we've two function calls here and take the minimum of the two.
• Else, we place the book on the next shelf. In this case, we make one function call.
• At last, we return the answer.
•  

Let’s try to code it now.

Program

#include <iostream>
#include <vector>
using namespace std;

// Function to try every possible arrangement of books to find the minimum height of the shelf.
int solver(vector<vector<int>> &books, int i, int currentWidth, int shelfHeight, int height, int shelfWidth)
{
   // If we have placed all the books then return height.
   if (i == books.size())
   {
       return height + shelfHeight;
   }
   
   // Add current book width to current shelf width.
   int width = currentWidth + books[i][0];
   int ans;
   
   // If the resultant width is less than ‘SHELF_WIDTH’, we can either place this book on the same shelf or keep it in the next shelf.
   if (width <= shelfWidth)
   {
       // Minimum height when the current book is kept on the same shelf.
       int sameShelf = solver(books, i + 1, width, max(shelfHeight, books[i][1]), height, shelfWidth);
       
       // Minimum height when the current book is kept on the next shelf.
       int nextShelf = solver(books, i + 1, books[i][0], books[i][1], height + shelfHeight, shelfWidth);
       
       // Next we see which will give us minimum height.
       ans = min(sameShelf, nextShelf);
   }
   // If the resultant width exceeds ‘SHELF_WIDTH’, then we keep this book on the next shelf.
   else
   {
       ans = solver(books, i + 1, books[i][0], books[i][1], height + shelfHeight, shelfWidth);
   }
   // Return minimum height.
   return ans;
}

//Function that returns Minimum height of shelf needed to fit all N books.
int minHeightShelf(vector<vector<int>> &books, int shelfWidth)
{
   // Call main solver Function.
   return solver(books, 1, books[0][0], books[0][1], 0, shelfWidth);
}

int main()
{
   int n;
   cout << "Enter the number of books: ";
   cin >> n;
   
   int shelfWidth;
   cout << "Enter the value of maximum shelf width: ";
   cin >> shelfWidth;
   
   cout << "Enter the Books width and height:\n";
   vector<vector<int>> books(n, vector<int>(2));
   for (int i = 0; i < n; i++)
   {
       cin >> books[i][0] >> books[i][1];
   }
   
   int ans = minHeightShelf(books, shelfWidth);
   cout << "The minimum height of shelf needed to fit all books is: " << ans << endl;
   return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input

Enter the number of books: 6
Enter the value of maximum shelf width: 5
Enter the Books width and height:
1 2
4 3
3 2
2 5
1 1
1 2

Output

The minimum height of the shelf needed to fit all the books is:  10

Time Complexity

O(2 ^ N), where ‘N’ is the number of books.

We have two choices for each book: we keep it on the next shelf or the same shelf. So roughly for each 'N' book, we will call the recursive function twice, resulting in exponential time complexity.

Space Complexity

O(N), where ‘N’ is the number of books.

Since at a particular time, there will be at max 'N' function calls in the stack.

Approach 2 - Dynamic Programming

The second approach to the problem is using Bottom-Up Dynamic programming.

To start, we'll place each book on the next shelf and then iterate over the previous 0 to i - 1 books and try to fit as many books as possible on the previous shelves.

As we are iterating i - 1(range 0 to N - 1) books back for each book, the time complexity will be O(N ^ 2) which is far better than exponential.

Let’s discuss the algorithm in detail now.

• First, we initialize an array ‘DP’ of size 'N + 1’ where DP[i] will denote the minimum height of the shelf after placing i^th book.
• We’ll set DP[0] = 0 and DP[1] = BOOK[0][1] (height of the first book).
• Then we’ll loop from the second book till the last. And for each book we’ll first place it in the next shelf, i.e., DP[i] = DP[i - 1] + book[i][1] (height).
• Next, we loop through the previous books and try to fit the current book.
• In the end, we return DP[N].

Program

#include <iostream>
#include <vector>
using namespace std;

// Function that returns minimum height of shelf needed to fit all N books.
int minHeightShelves(vector<vector<int>> &books, int shelfWidth)
{
   // Number of Books.
   int n = books.size();
   
   // If we have only one book to place then return the height of that book.
   if (n == 1)
       return books[0][1];
       
   // Initialize a ‘DP’ table where DP[i] represents the minimum height of the shelf when there are 1 to i books to place.
   int dp[n + 1];
   
   // If there is no book to place answer = 0.
   dp[0] = 0;
   
   // If we have one book to place, the answer is the height of that book.
   dp[1] = books[0][1];
   
   int height, width;
   
   // Now, we iterate from the second book up to the last one and compute the answer.
   for (int i = 2; i <= n; i++)
   {
       height = books[i - 1][1];
       width = books[i - 1][0];
       
       // In the worst case, we'll place the next book on the next shelf and hence we'll simply add its height to the previous minimum height.
       dp[i] = dp[i - 1] + height;
       
       // We then try to adjust this book to the previous levels.
       int j = i - 1;
       while (j > 0 && width < shelfWidth)
       {
           width += books[j - 1][0];
           
           // Check if the combined width does not exceeds SHELF_WIDTH.
           if (width > shelfWidth)
               break;
               
           // Update the max height.
           height = max(height, books[j - 1][1]);
           
           // Next we update our dp value after adjusting the book at j-1 level.
           dp[i] = min(dp[i], dp[j - 1] + height);
           j--;
       }
   }
   // Return DP[n].
   return dp[n];
}

int main()
{
   int n;
   cout << "Enter the number of books: ";
   cin >> n;
   
   int shelfWidth;
   cout << "Enter the value of maximum shelf width: ";
   cin >> shelfWidth;
   
   cout << "Enter the value of width and height for N books:\n ";
   vector<vector<int>> books(n, vector<int>(2));
   for (int i = 0; i < n; i++)
   {
       cin >> books[i][0] >> books[i][1];
   }
   
   int minHeight = minHeightShelves(books, shelfWidth);
   cout << "The minimum height of shelf needed to fit all the books is: " << minHeight << endl;
   return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input

Enter the number of books: 5
Enter the value of maximum shelf width: 5
Enter the Books width and height:
2 4
1 4
3 2
1 7
4 2

Output

The minimum height of the shelf needed to fit all the books is:  13

Time Complexity

O(N^2), where ‘N’ is the number of books.

Since for each ‘BOOK[i]’, we are iterating over all books from 0 to i - 1.

Space Complexity

O(N), where ‘N’ is the number of books. 

Since we are creating a ‘DP’ array of size ‘N’.

Check out Longest Common Substring

Key Takeaways

Working up a dynamic programming solution is always a challenge. But you can always figure out the DP solution once you have the idea of the problem and the recursive solution.

On the Coding Ninjas Platform, we have a variety of such problems and blogs. Additionally, Coding Ninjas recently introduced the Coding Ninjas Studio Test Series, a mainly developed test series for acing interviews.

Check out this problem - Minimum Coin Change Problem 

Thank you for taking the time to read this. I hope this blog has been helpful to you.