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.

Advertisements
Explore posts in the same categories: C++

Tags: , , ,

You can comment below, or link to this permanent URL from your own site.

One Comment on “Assembly line problem”

  1. aaa Says:

    Good program, and it runs too!!
    But please write neatly next time, it’s really difficult to understand right now..


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: