Question

Dynamic Programming

A company need to deliver n packages:

their due dates are{d[1],d[2],....,d[n]}, d[i]>=1

their necessary delivering days are{t[1],t[2],....,t[n]}, d[i]>=t[i]>=1

their profits are{p[1],p[2],...,p[n]},p[i] > 0,

The company can only delivery one package on on single day.

For example, a package d,t,p are 10,2,1. That means: If it is finished(2 days are used, 2 consecutive days are not need ) before or on day 10, the company will get its profit 1.

Eligible scheule plans for the above package are:

deliver it on day 7,8
deliver it on day 9,10
deliver it on day 7,10
...
...
...
many
...

Design an dynamic programming to help the company how to deliver these packages and they will get maximal profit.

Answer 1

 /*Please go through the pictures in the given order and at last see the code.Hope this helps.Thank you*/ import java.util.Arrays; import java.util.Comparator; class Job{ int dueDate; int deliveryDay; int profit; Job(int dueDate,int deliveryDay,int profit){ this.dueDate= dueDate; this.deliveryDay = deliveryDay; this.profit= profit; } } class FinishTimeComparator implements Comparator<Job>{ @Override  public int compare(Job arg0, Job arg1) { if(arg0.deliveryDay <= arg1.deliveryDay){ return -1; }else{ return 1; } } } public class DeliveringPackagesWithMaximumProfit { /**  * Sort the jobs by finish time.  * For every job find the first job which does not overlap with this job  * and see if this job profit plus profit till last non overlapping job is greater  * than profit till last job.  * @param jobs  * @return  */  public int maximum(Job[] jobs){ int T[] = new int[jobs.length]; FinishTimeComparator comparator = new FinishTimeComparator(); Arrays.sort(jobs, comparator); T[0] = jobs[0].profit; for(int i=1; i < jobs.length; i++){ T[i] = Math.max(jobs[i].profit, T[i-1]); for(int j=i-1; j >=0; j--){ if(jobs[j].deliveryDay <= jobs[i].dueDate){ T[i] = Math.max(T[i], jobs[i].profit + T[j]); break; } } } int maxVal = Integer.MIN_VALUE; for (int val : T) { if (maxVal < val) { maxVal = val; } } return maxVal; } public static void main(String args[]){ Job jobs[] = new Job[6]; jobs[0] = new Job(1,4,3); jobs[1] = new Job(2,6,5); jobs[2] = new Job(4,7,2); jobs[3] = new Job(6,8,6); jobs[4] = new Job(5,9,4); jobs[5] = new Job(7,10,8); DeliveringPackagesWithMaximumProfit mp = new DeliveringPackagesWithMaximumProfit(); System.out.println(mp.maximum(jobs)); } } 

Scheduting Packagen to get a aseman Profile (44) = (sue Date, delivery Day) Geen data Profit de delivery ng devem value pole 7 10 8 Delivery Day. Jobs accords Soothing the dure Date delivery - Profit Day Results 1

o TT i 2 3 4 5 6 7 8 9 10 Timeline overlap. Cágb a e 0 2 1 3 4 5 6 7 9 8 10 1 Cå , q ë does not overlap i starts from index 1 For every i j starts from the beginging. beginging. ed. f 0 1 2 3 Indese 4

od 1 Step by step procedure: ca ab uut (B) (5, 4) cano) they compare overlap. timeliner of a b. kle see that So, donot change ang anything Iteration a (1,4) b (2,6) c (4,7) e d e (6,8 15,9) (7,10) 4 00 op - compose Emelines of a c. They donot overlap. So, they can be executed together. So add profits of 'aac. į a b c edt 6 compose timelines of b (266) og e(4,7). They overlap. So, they can't be executed poralia

Iteration compose a 1,4) Ge (6,8). Do not oveslap a b c e d of (1) 156 15614181 Compose 6 (2,6) y e (6,8), Donot overlap are > bte Son we prefer ob onco a b c e d of Go To 160418 ji c (417) & 6 (6,8) oneslap. 8o, como not be executed parallely:

1 teration a b c e di 5 b 4 → alla) & d (5,9).donot overlap. 6(2,6) og d (5,9) - Overlap. c (47) & d (5,9) overlap. e (6,8 g d (5,9) - Overlap. teration aьс е 1 1 1 1 a (14) , f (710) 6 (26) 9 f (7,10) c (917) 9 F (710) e (68) a f (7,10) ► a 15,9 9 + (7, 10) 1 1 Compatible 11213 Compatible y es compatible but 10413 not compatible Not compatible

Result c e d a b of so'b q'F excecuting consecutively Mancomum profit. res Dediwring packages of