## Assembly line problem

The assembly line problem is a primitive example used to explain dynammic programming. I just learnt t in my “Digital Algorithms” Class. Here I am giving the implementation part of the problem.

The problem definition can be easily seen using the lord: http://www.google.com ðŸ˜‰

The solution is in c++ 4.3.2 (as many like to call it). The most important thing to notice is the indexing of the 2-D arrays i used. c++ compiler raises issues if you try to pass 2-D arrays with it’s second index variable (or not defined). For eg:

`int abc ( int a [2][]){...}Â //is incorrect `

So, rather cleverly I have used:

int abc ( int a [][2] ) {…}Â //is correct

The full code is:

`#include<iostream>`

using namespace std;

```
```void prnt_statns(int l[][2],int le,int n){

int i=le;

cout<<"line "<<i<<" station "<<n<<"\n";

for(int j=n-1;j>0;--j){

i=l[j][i-1];

cout<<"line "<<i<<" station "<<j<<"\n";

}

}

void fast_way(int a[][2],int t[][2],int e[],int x[],int n){

int f1[n],f2[n],l[n][2],fe,le;

f1[0]=e[0]+a[0][0];

f2[0]=e[1]+a[0][1];

for(int j=1;j<n;++j){

if( (f1[j-1]+a[j][0]) <= (f2[j-1]+t[j-1][1]+a[j][0]) ){

f1[j]=f1[j-1]+a[j][0];

l[j][0]=1;

}

else{

f1[j]=f2[j-1]+t[j-1][1]+a[j][0];

l[j][0]=2;

}

if( (f2[j-1]+a[j][1]) <= (f1[j-1]+t[j-1][0]+a[j][1]) ){

f2[j]=f2[j-1]+a[j][1];

l[j][1]=2;

}

else{

f2[j]=f1[j-1]+t[j-1][0]+a[j][1];

l[j][1]=1;

}

}

if( (f1[n-1]+x[0]) <= (f2[n-1]+x[1]) ){

fe=f1[n-1]+x[0];

le=1;

}

else{

fe=f2[n-1]+x[1];

le=2;

}

prnt_statns(l,le,n);

}

`int main(){`

cout<<"This program gives the fastest way through a factory of n machines..\n";

cout<<"Enter number of machines.. ";

int n,i;

n=6;//cin>>n;

int a[n][2],t[n-1][2],e[2],x[2];

cout<<"Enter the entry times..\n1. ";

e[0]=2;//cin>>e[0];

cout<<"2. ";

e[1]=4;//cin>>e[1];

cout<<"Enter the exit times..\n1. ";

x[0]=3;//cin>>x[0];

cout<<"2. ";

x[1]=2;//cin>>x[1];

cout<<"Enter the station times of row 1:\n";

//a[0][]={7,9,3,4,8,4};//

for(i=0;i<n;++i) cin>>a[i][0];

cout<<"Enter the station times of row 2:\n";

//a[1]={8,5,6,4,5,7};//

for(i=0;i<n;++i) cin>>a[i][1];

cout<<"Enter transaction times from row 1:\n";

//t[0]={2,3,1,3,4};//

for(i=0;i<n-1;++i) cin>>t[i][0];

cout<<"Enter transaction times from row 2:\n";

//t[1]={2,1,2,2,1};//

for(i=0;i<n-1;++i) cin>>t[i][1];

fast_way(a,t,e,x,n);

return 0;

}

Hope you get it . If any problem occurs regarding the code, mind to comment here…

The logic used here is the general Dynammic Programming approach.

**Explore posts in the same categories:**C++

**Tags:** assembly line, c++, dynamic programming, implementation

April 15, 2011 at 2:55 PM

Good program, and it runs too!!

But please write neatly next time, it’s really difficult to understand right now..