A box of pre-cooked food contains N dishes and each dish has 2 properties, its Protein content and its Fat content. We need to select a non-empty subset of these N dishes such that the ratio of total Protein content to total Fat content in these selected subset of dishes is equal to a given target T.

Answer Yes if possible, No otherwise.

Constraints: 1<=N<=50 1<=T,Protein_i,Fat_i<=10

Eg1:

N=3,T=5

[[8,1],[1,1],[2,1]] where first index corresponds to protein content and second is fat content. Answer is "Yes" because selecting 1st and 3rd dish yields (8+2)/(1+1) = 5.

Eg2:

N=3,T=6

[[8,1],[1,1],[2,1]]. Answer is "No"

I don't think bitmask would work given that N can be upto 50. Any other solutions to this problem?

Given N processes with Arrival times and Processing times, calculate and print minimum number of CPUs required if maximum allowed Turnaround time for each process is 10 units.

Turnaround time = Waiting time in queue + Processing time

Each processor has its own processing queue. Processes cannot be preempted.

Maximum number of CPUs allowed is 5. If more than 5 required, then print -1.

Example:

Task Arrival_time Processing_time
T1   2            7
T2   3            5

Ans: 2

I was thinking of a greedy approach initially (which turned out to be wrong) based on the following observations (which might be wrong)

• A process which with earlier arrival time should always get scheduled earlier than a process with later arrival time — no benefit in scheduling it later

• It is always better to schedule a process on a CPU with longer queue (as long as the Turnaround time condition is met), reason being, we will have a free resource available earlier, i.e. tightest fit match — Eg: [Arrival time, Processing time] If we have CPU1 queue to be [0,2][2,5] and CPU2 [0,3], if a job [3,4] comes in, schedule it on CPU1. We will have a free resource (CPU2) — available earlier — i.e. from 3 onwards, but if we schedule on CPU2, then we only have free resource (CPU1) from 5 onwards.

Approach:

- At each arrival time, sort jobs based on Processing time.
- Maintain a decreasing load list of CPUs (i.e. CPU with highest load is first on the list)
- Allocate jobs to CPUs in the given order, highest processing time job to first possible busiest CPU, reorder CPUs if necessary after allocating, if cannot allocate to existing CPUs, create new CPU (if <= 5) and allocate job to it

Though this might work well in an online setting (i.e. when we don't know the all the jobs and times in advance), it is suboptimal when we know that information. Eg:

Task Arrival_time Processing_time
T1   0            3
T2   0            3
T3   3            8

The approach outlined would schedule T1 and T2 on CPU1, and when T3 arrives, it gets scheduled on CPU2 (which gets created). If we'd known that we would need CPU2, we could've as well scheduled T2 on CPU1, which is better.

Hence, I realized that I may not be utilizing the <=5 CPU part of the question. Now I think the approach should be to try a solution with 1 CPU first, if not possible, then with 2 CPUs,.. Now for each arrival time, sort jobs in ascending order of processing time and allocate it in that order to the free-est CPU — i.e. least turnaround time — from amongst the k CPUs where k = 1 to begin with, 2 if solution with k=1 is not possible and so on.

If this too is wrong, what could be the right approach to this problem?