Question

There are n tasks to complete. Each task first needs to be preprocessed on a supercomputer and then finished on one of n processors. Task i requires pi seconds of preprocessing on the supercomputer followed by fi seconds on some processor to complete. Note that tasks are fed to the supercomputer sequentially but can be executed in parallel on different processors once they have been preprocessed. The process terminates when all tasks have been completed. The duration of the process is the total time until termination. Give an efficient algorithm that determines an ordering of the tasks for the supercomputer that minimizes the duration of the process, as well as the minimum duration.

Answer 1

Answer:

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int main()

{

ll i,n,j,s;

cout<<"Enter size of array: ";

cin>>n;

ll a[n];

cout<<"Enter elements of array: ";

s=0;

for(i=0;i<n;i++)

{

cin>>a[i];

s+=a[i];

}

if(s%3!=0)

{

cout<<"No";

return 0;

}

ll dp[n][s/3+1];

for(i=0;i<=s/3;i++)

{

if(i==a[0])

dp[0][i]=1;

else

dp[0][i]=0;

}

for(i=0;i<n;i++)

dp[i][0]=1;

for(i=1;i<n;i++)

for(j=0;j<=s/3;j++)

{

if(j<a[i])

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

else

dp[i][j]=dp[i-1][j]||dp[i-1][j-a[i]];

}

if(dp[n-1][s/3]==0)

{

cout<<"No";

return 0;

}

ll vis[n];

for(i=0;i<n;i++)

vis[i]=0;

ll curr=s/3;

ll indx=n-1;

ll c=0;

while(indx>0)

{

if(dp[indx][curr]==1&&(curr-a[indx]>=0&&dp[indx-1][curr-a[indx]]==1))//include indx

{

vis[indx]=1;

curr=curr-a[indx];

c++;

}

indx--;

}

if(dp[0][curr]==1){

vis[0]=1;

c++;}

ll b[n-c];

ll k=0;

for(i=0;i<n;i++)

{

if(vis[i]==0)

b[k++]=a[i];

}

ll dp1[k][s/3+1];

for(i=0;i<=s/3;i++)

{

if(i==b[0])

dp1[0][i]=1;

else

dp1[0][i]=0;

}

for(i=0;i<k;i++)

dp1[i][0]=1;

for(i=1;i<k;i++)

for(j=0;j<=s/3;j++)

{

if(j<b[i])

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

else

dp1[i][j]=dp1[i-1][j]||dp1[i-1][j-b[i]];

}

if(dp1[k-1][s/3]==0)

{

cout<<"No";

return 0;

}

else

cout<<"Yes";

}

Explanation: