```
// DANI HOROWITZ
// NOVEMBER 2004
/***************************************************************************/
/***************************************************************************/
// CSC 155 Project 2 Dynamic Programming
// Assigned 11/02/2004
// Due : 11/16/2004
//
// This file contains the description of the following two problems
//
// 1) Shortest path on a rectangular grid
// 2) Partitioning a set of elements S into two subsets A and B such that the
// sum total of the value associated with the elements of A and that of
// B are equal (Extra Credit)
//
// Problem 1:
//
// Shortest path on a rectangular grid
//
// You are given a rectangular grid consisting of mn points (i.e. m points on the
// x-axis and n points on the y-axis. Let the co-ordinates of these mn grid points
// be (1,1),(1,2),(1,3),..., (1,n), (2,1), (2,2), ..., (2,n), ... (m,1), ...(m,n).
// You are told that every grid point (i,j) is connected only to the four adjacent
// grid points (i-1,j), (i,j-1), (i+1, j) and (i, j+1). Each link that connects
// a grid point (i,j) with its neighbor is associated with a link distance.
// The link distance between the grid point (i,j) and the grid point to its right
// (i, j+1) is stored in a 2-dimensional array Right[i,j] and the link distance
// between the grid point (i,j) and the grid point above it (i+1,j) is stored in
// a 2-dimensional array Above[i,j].
// You are told that to begin with you are at grid point (1,1) and your objective
// is to reach the grid point (m,n) by choosing the shortest path. In addition,
// you are told at any grid point (i,j) you are allowed to either move to the grid
// point (i, j+1) immediately to your right or the grid point (i+1, j) one
// immediately above you.
// Write a dynamic program to determine the shortest path from grid point (1,1) to
// grid point (m, n).
// You need to write a program to solve the above problem using dynamic
// programming techniques discussed in class.
//
// int *Rectangular_Shortest_Path(int startx, int starty, int endx, int endy,
// int Right[][], int Above[][])
//
// Given the grid points with co-ordinates (startx, starty) and (endx, endy),
// the above function returns an array containing the shortest path from
// (startx, starty) to (endx, endy)
//
// Problem 2:
//
// Partitioning a set of elements S into two subsets A and B such that the
// sum total of the value associated with the elements of A and that of
// B are equal (Extra Credit)
// You are given an integer array S of n elements, you need to partition the
// elements in S into two arrays A and B such that the sum of the elements in A
// equals the sum of the elements in B
//
// You need to write a program to solve the above problem using dynamic
// programming techniques discussed in class.
//
// void Partition(int *S, int *A, int *B)
//
// Example : suppose the array S contains the items {20, 15, 35, 45, 55, 30}
// then the program partitions the elements in S into two arrays
// A = {20, 15, 35, 30} and B = {45, 55}. If the set S cannot be partitioned
// into two equal sub-arrays set both A and B to empty arrays.
//
#include <iostream.h>
int *Rectangular_Shortest_Path(int , int , int , int , int[][6], int[][6]);
void Partition(int *S, int *A, int *B);
int *Rectangular_Shortest_Path(int startx, int starty, int endx, int endy,
int r[][6], int a[][6])
{
// I could find no easy way to dynamically create a 2D array in C++
int distance[10][10]; // keep track of distances to get to each point
int path[10][10]; // keep track of the best paths
/***************************************************************************/
/***************************************************************************/
int size = (endx-startx)+(endy-starty); // size of our shortest path array
int* shortest_path = new int[size]; // it will take 8 steps to get from (0,0)->(5,5)
cout << "It will take " << size << " steps" << endl;
/***************************************************************************/
/***************************************************************************/
// populate our starting place
distance[startx][starty] = 0;
// populate bottom distance row
for (int x=startx+1; x<=endx; x++)
{
distance[x][starty] = distance[x-1][starty] + r[x-1][starty];
cout << "We went right to get to (" << x << "," << starty << ") in " << distance[x][starty] << " units" << endl;
}
// populate leftmost distance row
for (int y=starty+1; y<=endy; y++)
{
distance[startx][y] = distance[startx][y-1] + a[startx][y-1];
cout << "We went up to get to (" << startx << "," << y << ") in " << distance[startx][y] << " units" << endl;
}
/***************************************************************************/
/***************************************************************************/
cout << endl;
for (int y=starty+1; y<=endy; y++) // go down each column
{
for (int x=startx+1; x<=endx; x++) // go across each row
{
int distance_up = distance[x][y-1] + a[x][y-1]; // calculate weight to get to (x,y) from coordinate below it
int distance_right = distance[x-1][y] + r[x-1][y]; // calculate weight to get to (x,y) from coordinate to left of it
if (distance_up < distance_right) // it's better to move up
{
distance[x][y] = distance_up; // populate our distance array
path[x][y] = 1; // populate our path array
cout << "If we go up to get to (" << x << "," << y << ") we can do it in a weight of " << distance[x][y] << " units" << endl;
}
else // it's better to move right
{
distance[x][y] = distance_right; // populate our distance array
path[x][y] = 0; // populate our path array
cout << "If we go right to get to (" << x << "," << y << ") we can do it in a weight of " << distance[x][y] << " units" << endl;
}
}
}
/***************************************************************************/
/***************************************************************************/
x = endx;
y = endy;
int n=0;
cout << endl << "Working backwards ..." << endl;
// now that we have all of the smaller problems solved to calculate the optimal weight to get to every point on the grid,
// let's figure out how to get from (5,5)->(1,1)
while (x >= startx && y >= starty) // loop so long as both coordinates are >= 1
{
if (x > startx && y > starty)
{
// we are not working in the first row or first column,
// which means that we have an opportunity of going left or down, whichever is best
if ((distance[x-1][y]+r[x-1][y]) < (distance[x][y-1]+a[x][y-1]))
{
cout << "Go left from (" << x << "," << y << ") for " << distance[x][y] << " units left" << endl;
x--; // move one unit left
}
else
{
cout << "Go down from (" << x << "," << y << ") for " << distance[x][y] << " units left" << endl;
y--; // move one unit down
}
}
else
{
if (x == startx) // we are somewhere in the left column
{
// we don't have a choice, we can only move down
cout << "Go down from (" << x << "," << y << ") for " << distance[x][y] << " units left" << endl;
y--;
}
else // we are somewhere in the bottom row
{
// we don't have a choice, we can only move left
cout << "Go left from (" << x << "," << y << ") for " << distance[x][y] << " units left" << endl;
x--;
}
}
shortest_path[n] = path[x][y]; // populate our shortest path array
n++;
}
cout << endl;
/***************************************************************************/
/***************************************************************************/
return shortest_path; // return the shortest path BACKWARDS!
}
void Partition(int *S, int *A, int *B)
{
// please fill in your code here and remove the statement "return"
return;
}
void main()
{
int Right[6][6]; // entry Right[i][j] contains the link distance
// between grid point (i,j) to (i+1, j);
int Above[6][6]; // entry Above[i][j] contains the link distance
// between grid point (i,j) to (i, j+1);
int *shortest_path; // the array for storing the shortest path
int S[10]; // set of items you would like to partition
int A[10]; // the first half of the partition
int B[10]; // the second half of the partition
//
// read the inputs for the 2-dimensional arrays Right and Above
//
for (int i=1; i< 6; i++)
{
for (int j=1; j < 6; j++)
{
cout << "Please enter the link distance : Right[" << i << "," << j << "]\n";
cin >> Right[i][j];
cout << "Please enter the link distance : Above[" << i << "," << j << "]\n";
cin >> Above[i][j];
}
}
shortest_path = Rectangular_Shortest_Path(1,1,5,5, Right, Above);
/*
//
// read the inputs for the set S
//
for (int i=1; i< 10; i++)
{
cout << "Please enter the " << i << "th item in S\n";
cin >> S[i];
}
Partition(S, A, B);
*/
}
```