## Chapter 9: Dynamic Programming II

### Activity 22: Maximizing Profit

In this activity, we will optimize our inventory for sale to maximize our profits. Follow these steps to complete the activity:

- Let's begin by including the following headers:
#include <iostream>

#include <vector>

using namespace std;

- First, we will define a structure,
**Product**, that encapsulates the data associated with each item:struct Product

{

int quantity;

int price;

int value;

Product(int q, int p, int v)

: quantity(q), price(p), value(v) {}

};

- Next, we will handle the input in the
**main()**function and populate an array of the**Product**type:int main()

{

int N, budget, capacity;

cin >> N >> budget >> capacity;

vector<Product> products;

for(int i = 0; i < N; i++)

{

int quantity, cost, value;

cin >> quantity >> cost >> value;

products.push_back(Product(quantity, cost, value));

}

...

return 0;

}

- As with any DP algorithm, we must now define the states and base cases. We know that the subset of items that form the final result must match the following criteria:
– The sum of the

**cost**of all the products in the subset must not exceed**budget**.– The sum of the

**quantity**of all the products in the subset must not exceed**capacity**.– The sum of the

**value**of all the products in the subset must be maximized.Given these criteria, we can see that each state can be defined by the following parameters:

– The current item being considered

– The number of units previously purchased

– The total cost of the purchased items

– The total profit gained after selling the products at retail value

We can also conclude that a search will terminate when:

– All the items have been considered

– The total cost exceeds the budget

– The total number of units exceeds the capacity

Like the traditional 0-1 knapsack problem, we will consider each item from

**0**to**N-1**linearly. For each item at index**i**, our states can transition in one of two ways: by either including the current item or leaving it. Writing the recursive logic in pseudocode may look like this:F(i, count, cost, total):

I –> The index of the current item

Cost –> The total money spent

count –> The number of units purchased

total –> The total profit value of the chosen items

Base cases:

if i = N: return total

if cost > budget: return 0

if count > capacity: return 0

Recurrence:

F(i, count, cost, total) = maximum of:

F(i + 1, count + quantity[i], cost + price[i],

total + value[i]) – Include the item

AND

F(i + 1, count, cost, total) – Leave as-is

As shown in the preceding code, the recurrence relation is defined according to the values of

**i**,**count**,**cost**, and**total**. Converting this logic from top down to bottom up can be done like so:Base case:

DP(0, 0, 0) = 0 [Nothing has been chosen yet]

For i = 1 to N:

Product -> quantity, price, value

For cost = 0 to budget:

For count = 0 to capacity:

If price is greater than cost OR

quantity is greater than count:

DP(i, cost, count) = DP(i-1, cost, count)

Otherwise:

DP(i, cost, count) = maximum of:

DP(i-1, cost, count)

AND

DP(i-1, cost – price, count – quantity) + value

In other words, each state is described according to the current index, total cost, and total count. For each pair of valid

**cost**and**count**values, the current result for an item at index**i**will be equal either to the maximum subset sum that was found for the same values of**cost**and**count**at index**i – 1**(that is,**DP[i – 1][cost][count]**) or the sum of the current item's**value**with the maximum sum at index**i – 1**with**cost**and**count**equal to what they would have been prior to including the item (that is,**DP[i - 1][cost – price][count – quantity] + value**). - We can code the preceding logic as follows:
vector<vector<vector<int>>> DP(N + 1, vector<vector<int>>(budget + 1, vector<int>(capacity + 1, 0)));

for(int i = 1; i <= N; i++)

{

Product product = products[i-1];

for(int cost = 0; cost <= budget; cost++)

{

for(int count = 0; count <= capacity; count++)

{

if(cost < product.price || count < product.quantity)

{

DP[i][cost][count] = DP[i-1][cost][count];

}

else

{

DP[i][cost][count] = max

(

DP[i-1][cost][count],

DP[i-1][cost – product.price][count – product.quantity] + product.value

);

}

}

}

cout << DP[N][budget][capacity] << endl;

}

As you can see, the implementation is equivalent to the 0-1 knapsack solution with an additional dimension.

### Activity 23: Residential Roads

This activity has quite a few potential pitfalls if you do not approach it with some forethought. The most difficult aspect of it is the fact that it requires a number of distinct steps, and a careless mistake at any point can cause the entire program to fail. Therefore, it is recommended to approach the implementation step by step. The primary steps that are required are as follows:

- Handling the input
- Building the graph (finding adjacencies and weight values)
- Finding the shortest distances between graph nodes
- Reconstructing the edges in the shortest paths
- Redrawing the input grid

Since this is considerably lengthier than the other activities in this chapter, let's attack each of these steps individually.

**Step 0: Preliminary Setup**

Before we write any code related to input, we should decide how we want to represent our data in advance. The input we will receive is as follows:

- Two integers,
**H**and**W**, representing the height and width of the grid. - An integer,
**N**, representing the number of houses contained on the property. **H**strings of width**W**representing the map of the property. We can store this data as an**H**-element vector of strings.**H**rows of**W**integers representing the ruggedness of the terrain. We can store these values in an integer matrix.**N**lines containing two integers,**x**and**y**, representing the coordinates of each house. For this, we can create a simple structure called**Point**containing two integers,**x**and**y**.

Now, let's look at the implementation:

- Include the required headers and define some global constants and variables that we will need later in this problem. We will declare most of our data globally for the sake of convenience, but it is worth reiterating the point that this is generally considered bad practice within the context of a full-scale application:
#include <iostream>

#include <vector>

using namespace std;

const int UNKNOWN = 1e9;

const char EMPTY_SPACE = '.';

const string roads = "-|/\\";

struct Point

{

int x;

int y;

Point(){}

Point(int x, int y) : x(x), y(y) {}

};

int N;

int H, W;

vector<string> grid;

vector<vector<int>> terrain;

vector<vector<int>> cost;

vector<Point> houses;

**Step 1: Handling the Input** - Since there is a fair amount of input required for this problem, let's contain it all in its own function,
**Input()**, which will return void:void Input()

{

cin >> H >> W;

cin >> N;

grid.resize(H);

houses.resize(N);

terrain.resize(H, vector<int>(W, UNKNOWN)); cost.resize(H, vector<int>(W, UNKNOWN));

// Map of property

for(auto &row : grid) cin >> row;

// Terrain ruggedness

for(int I = 0; i < H; i++)

{

for(int j = 0; j < W; j++)

{

cin >> terrain[i][j];

}

}

// House coordinates

for(int i = 0; i < N; i++)

{

cin >> houses[i].x >> house[i].y;

// Set house labels in grid

grid[houses[i].y][houses[i].x] = char(i + 'A');

}

}

**Step 2: Building the Graph**The problem description states the following:

- A road can be built between two houses if and only if there is a direct horizontal, vertical, or diagonal path between them.
- Roads may not be built across bodies of water, mountains, forests, and so on.
- The cost of building a road between two houses is equal to the sum of ruggedness values on the path between them.

To test the first condition, we simply need to compare the coordinates of two points and determine whether any of the following three conditions are true:

**A.x = B.x**(there is a horizontal line between them)**A.y = B.y**(there is a vertical line between them)**| A.x – B.x | = | A.y – B.y |**(there is a diagonal line between them)

Now, let's get back to our code.

- To do this, let's write a function
**DirectLine()**, that takes two points,**a**and**b**, as arguments and returns a Boolean:bool DirectLine(Point a, Point b)

{

return a.x == b.x || a.y == b.y || abs(a.x – b.x) == abs(a.y – b.y);

}

- To handle the second and third cases, we can simply perform a linear traversal from point
**a**to point**b**in the grid. As we consider each point in the grid, we can accumulate the sum of values contained in the terrain matrix. As we do this, we can simultaneously check the character in**grid[a.y][a.x]**, terminating it as soon as we encounter a character that is not equal to**EMPTY_SPACE**(that is, '**.**'). If at the end of the traversal point**a**is equal to point**b**, we will store the sum we acquired in the**cost**matrix; otherwise, we have determined that there is no adjacency between**a**and**b**, in which case we return**UNKNOWN**. We can do this using the**GetCost()**function, which takes two integers,**start**and**end**, as arguments. These represent the indices of**a**and**b**, respectively, and return an integer:int GetCost(int start, int end)

{

Point a = houses[start];

Point b = houses[end];

// The values by which the coordinates change on each iteration

int x_dir = 0;

int y_dir = 0;

if(a.x != b.x)

{

x_dir = (a.x < b.x) ? 1 : -1;

}

if(a.y != b.y)

{

y_dir = (a.y < b.y) ? 1 : -1;

}

int cost = 0;

do

{

a.x += x_dir;

a.y += y_dir;

cost += terrain[a.y][a.x];

}

while(grid[a.y][a.x] == '.');

return (a != b) ? UNKNOWN : res;

}

- The final line requires that we define
**operator !=**in our**Point**struct:struct Point

{

......

bool operator !=(const Point &other) const { return x != other.x || y != other.y; }

}

- Now, let's create the following
**GetAdjacencies()**function:void GetAdjacencies()

{

for(int i = 0; i < N; i++)

{

for(int j = 0; j < N; j++)

{

if(DirectLine(houses[i], houses[j])

{

cost[i][j] = cost[j][i] = GetCost(i, j);

}

}

}

}

**Step 3: Finding the Shortest Distances between Nodes**The problem states that two houses should be connected by a road that is on the path that minimizes the cost of reaching the exit point. For this implementation, we will use the Floyd-Warshall algorithm. Let's get back to our code:

- Let's define a function,
**GetShortestPaths()**, that will handle both the implementation of Floyd-Warshall as well as the path's reconstruction. To handle the latter case, we will maintain a*N x N*integer matrix called**next**that will store the index of the next point on the shortest path from nodes**a**and**b**. Initially, its values will be set to the existing edges in the graph:void GetShortestPaths()

{

vector<vector<int>> dist(N, vector<int>(N, UNKNOWN));

vector<vector<int>> next(N, vector<int>(N, UNKNOWN));

for(int i = 0; i < N; i++)

{

for(int j = 0; j < N; j++)

{

dist[i][j] = cost[i][j]

if(dist[i][j] != UNKNOWN)

{

next[i][j] = j;

}

}

dist[i][j] = 0;

next[i][i] = i;

}

...

}

- We will then perform the standard implementation of Floyd-Warshall, with one additional line in the innermost loop setting
**next[start][end]**to**next[start][mid]**every time we find a shorter distance between**start**and**end**:for(int mid = 0; mid < N; mid++)

{

for(int start = 0; start < N; start++)

{

for(int end = 0; end < N; end++)

{

if(dist[start][end] > dist[start][mid] + dist[mid][end])

{

dist[start][end] = dist[start][mid] + dist[mid][end];

next[start][end] = next[start][mid];

}

}

}

}

**Step 4: Reconstructing the Path**With the data that we obtained in the

**next**matrix, we can easily reconstruct the points on each path in a similar way to the reconstruction approaches for the LCS or 0-1 Knapsack problems. For this purpose, we will define another function,**GetPath()**, that has three parameters—two integers,**start**and**end**, and a reference to the**next**matrix — and returns an integer vector containing the node indices of the path:vector<int> GetPath(int start, int end, vector<vector<int>> &next)

{

vector<int> path = { start };

do

{

start = next[start][end];

path.push_back(start);

}

while(next[start][end] != end);

return path;

}

- Returning to
**GetShortestPaths()**, we will now add a loop underneath our implementation of Floyd-Warshall that calls**GetPath()**and then draws lines in the grid corresponding to each pair of points in the path:for(int i = 0; i < N; i++)

{

auto path = GetPath(i, N – 1, next);

int curr = i;

for(auto neighbor : path)

{

DrawPath(curr, neighbor);

curr = neighbor;

}

}

**Step 5: Redrawing the Grid** - Now, we must draw the roads in the grid. We will do this in another function,
**DrawPath()**, which has the**start**and**end**parameters:void DrawPath(int start, int end)

{

Point a = houses[start];

Point b = houses[end];

int x_dir = 0;

int y_dir = 0;

if(a.x != b.x)

{

x_dir = (a.x < b.x) 1 : -1;

}

if(a.y != b.y)

{

y_dir = (a.y < b.y) 1 : -1;

}

……

}

- We will need to choose the correct character corresponding to the orientation of each road. To do this, we will define a function,
**GetDirection()**, that returns an integer corresponding to an index in the**roads**string we defined at the beginning ("**-|/\**"):int GetDirection(int x_dir, int y_dir)

{

if(y_dir == 0) return 0;

if(x_dir == 0) return 1;

if(x_dir == -1)

{

return (y_dir == 1) ? 2 : 3;

}

return (y_dir == 1) ? 3 : 2;

}

void DrawPath(int start, int end)

{

……

int direction = GetDirection(x_dir, y_dir);

char mark = roads[direction];

……

}

- We can now perform a linear traversal from
**a**to**b**, setting each cell in the grid to**mark**if its value is**EMPTY_SPACE**. Otherwise, we must check to see whether the character in the cell is a road character of a different orientation, in which case we set it to**+**:do

{

a.x += x_dir;

a.y += y_dir;

if(grid[a.y][a.x] == EMPTY_SPACE)

{

grid[a.y][a.x] = mark;

}

else if(!isalpha(grid[a.y][a.x]))

{

// If two roads of differing orientations intersect, replace symbol with '+'

grid[a.y][a.x] = (mark != grid[a.y][a.x]) ? '+' : mark;

}

}

while(a != b);

- All that is left is to call our functions in
**main()**and print the output:int main()

{

Input();

BuildGraph();

GetShortestPaths();

for(auto it : grid)

{

cout << it << endl;

}

return 0;

}