What are virtual machines?

What is the maximal profit that M machines can earn over W weeks if each machine can manufacture either product A (300TL profit) or product B (500TL profit) for a given week, knowing that 30% of machines that manufacture product A and 60% of machines that manufacture product B wear out each week (an

• Consider the operation of a machine shop in which there are M machines. These machines can be used to manufacture two different kinds of products, A and B. The total amount of product A manufactured by one machine in one week will be sold for a profit of 300TL and the total amount of product B manufactured by one machine in a week will be sold for a profit of 500TL. However after each week's operation, 30% of the machines making product A will become worn out beyond repair, whereas 60% of the machines making product B will become worn out beyond repair. Take the ceiling function to guarantee the numbers of machines are integers. Suppose that machines are assigned to manufacture one of the two kinds of products on a weekly basis. Our question is: over a period of W weeks, how should the machines be allocated to products A and B such that the total profit is maximized? Your task: Give a recursive formula for computing the maximum profit, and from that, deduce a time-efficient algorithm in pseudocode format, for solving the problem. An algorithm without recursive formula is not worth any marks. Dynamic programming must be used. [Hint: there should not be any idle machines in the W weeks.]

• Answer:

  Explanation The problem you've provided is an optimization problem and thus makes a perfect candidate for dynamic programming. However, the problem can be quite tricky to formulate if you are not experienced with dynamic programming.  Experience gives you the intuition to know what to use as your recurrence.  Since you're asking the question, I'll assume that you have only a passing understanding of dynamic programming.  As such, I'll try to explain the "why" of my process as much as possible.  If my approach is still not clear, please feel free to ask questions. So, the first step in solving a problem with dynamic programming is to develop the recursive formula.  To develop the recursive formula, we must identify whether the problem exhibits http://en.wikipedia.org/wiki/Optimal_substructure.  Suppose we have 10 machines and 5 weeks.  Can we determine the maximum profit using solutions to smaller instances of the original problem?  If so, then our problem exhibits optimal substructure. Suppose we try to calculate the maximum profit for 10 machines working for a single week.  We can do that by making each machine manufacture product B.  Since we are concerned only with a single week, we don't care how many machines wear out. Now, what happens when we have more than one week?  We can't just use the greedy solution for the first week anymore.  We have to be mindful of how our decisions in week 1 affect week 2, 3, ... etc. If we assign 1 machine during week 1 to manufacture product A and 9 machines to manufacture product B, then 30% of the machines manufacturing product A will wear out and 60% of the machines manufacturing product B will wear out, leaving us with 5 machines total at the start of week 2.  The profit for week 2 can be calculated in a similar manner, only now we have 5 machines instead of 10.  In other words, we have a smaller instance of the original problem. But how do we know how many machines to assign to manufacture product A and how many to assign to manufacture product B?  The short answer is that we don't.  So we try every possibility.  We assign 1 machine to manufacture product A and 9 machines to manufacture product B.  Then we assign 2 machines to manufacture product A and assign 8 machines to manufacture product B.  And so on... Then, we find whichever assignment produced the maximum profit. Dynamic programming essentially is brute force, done cleverly.  Thus, it makes sense that we have a brute force aspect to our solution.  The clever part is that we identify optimal substructure.  Once we've identified optimal substructure, we can solve all possible subproblems in order of smallest problem to biggest problem.  By doing it that way, we avoid recomputing values that we already know, and that is how we beat the brute force solution. So now that we have a basic idea of how to formulate the recurrence, let's try to to write our recursive formula. The goal of the problem is to find the maximum profit.  Thus, we start our recursive formula by defining a function, [math]P[/math], which returns the maximal profit for some input. So what input values dictate how much profit we make?  It should be pretty clear that the number of weeks we have is one input variable.  I'll use the variable [math]w[/math] to denote the number of weeks we have.  It should also be clear that the number of machines we have will also influence how much profit we make.  I'll use the variable [math]m[/math] to denote the number of machines we have. Thus, we want to compute: [math]P(w, m)[/math] Reading my answer, this should make sense.  However, it took some thought to figure out the best way to represent the input variables for [math]P[/math].  I debated whether the input variables would include the number of machines we were assigning to manufacture product A and B, etc.  I realized that every machine we had would either be functioning or worn out, and at the start of a week, we only needed to know how many machines we had available.  Eventually, I arrived at the notation above. Now, let's write the recurrence.  At a high level, we have: [math]P(w, m) =[/math] [math]\max (currentProfit + futureProfit)[/math] Let's refine that definition.  The max value we are calculating is the maximum profit over every possible assignment of machines during the current week.  Read that sentence a few times until you understand it.  Thus, we have: [math]P(w, m) = max_{0 \leq i \leq m}[/math][math](300i + (500(m - i))[/math][math]+ P(w - 1, \lfloor 0.7i \rfloor + \lfloor 0.4(m - i) \rfloor)[/math] Whoa!  Let's dissect this. The variable [math]i[/math] represents the number of machines that we assign to manufacture product A.  We can assign [math]0[/math] to [math]m[/math] machines to manufacture product A.  That explains the limits of our [math]\max[/math] computation. The amount of profit we will make for the current week will be 300 times the number of machines that manufacture product A plus 500 times the number of machines that manufacture product B.  (The number of machines that produce product B is [math](m - i)[/math].)  This is because we earn 300TL for product A and 500TL for product B. Then, we add the maximum amount of profit we can make for the future weeks.  This is simply a recursive call.  We decrease the week number by [math]1[/math] since we want to know profits for the remaining weeks.  Then, we compute how many machines continue to function after the current week.  If we lose 30% of the machines that manufacture product A (rounded up), then that leaves us with 70% of those machines (rounded down).  If we lose 60% of the machines that manufacture product B (rounded up), then that leaves us with 40% of those machines (rounded down).  The sum of machines that manufacture product A and B is the number of machines left.  Notice that we use the floor operator to round down. Now that we have the recursive formula, we can rather simply solve the problem.  We create a table that is [math]w \times m[/math] in size.  Then we iterate from smaller values of [math]w[/math] and [math]m[/math] to larger values.  We do this because solving for [math]table[w][m][/math] requires that we look at smaller values of [math]w[/math] and [math]m[/math], so we want to make sure that we've solved those sub-problems first. There are two ways to solve the problems in order from the small problems to the large problems.  We can use a bottom-up approach, or we can do a top-down approach (memoization). Time and space complexity The algorithm builds a table with [math]w[/math] rows and [math]m[/math] columns.  Each cell in the table takes [math]\Theta(m)[/math] time to compute (since we try [math]\Theta(m)[/math] different machine assignments for a given week). Thus, the overall run-time complexity is [math]\Theta(wm^2)[/math], and the overall space complexity is [math]\Theta(wm)[/math], where [math]w[/math] is the number of weeks and [math]m[/math] is the number of machines. Java code (Bottom-up approach) public class MachineMaxProfit { private static final int PROFIT_MACHINE_TYPE_A = 300; private static final int PROFIT_MACHINE_TYPE_B = 500; private static final float PERCENTAGE_DIE_MACHINE_TYPE_A = 0.3f; private static final float PERCENTAGE_DIE_MACHINE_TYPE_B = 0.6f; public static void main(String[] args) { int weeks = 5; int numMachines = 10; int maxProfit = computeMaxProfit(weeks, numMachines); System.out.println("The maximum profit for " + numMachines + " machine(s) operating for " + weeks + " week(s) is " + maxProfit + "."); } public static int computeMaxProfit(int numWeeks, int numMachines) { if (numWeeks <= 0 || numMachines <= 0) { return 0; } int[][] maxProfits = new int[numWeeks + 1][numMachines + 1]; for (int currentWeek = 1; currentWeek <= numWeeks; ++currentWeek) { for (int currentMachines = 1; currentMachines <= numMachines; ++currentMachines) { int maxProfit = 0; for (int numMachinesTypeA = 0; numMachinesTypeA <= currentMachines; ++numMachinesTypeA) { int numMachinesTypeB = currentMachines - numMachinesTypeA; int numMachinesRemainingTypeA = (int)Math.floor(numMachinesTypeA * (1 - PERCENTAGE_DIE_MACHINE_TYPE_A)); int numMachinesRemainingTypeB = (int)Math.floor(numMachinesTypeB * (1 - PERCENTAGE_DIE_MACHINE_TYPE_B)); int currentWeekProfit = (PROFIT_MACHINE_TYPE_A * numMachinesTypeA) + (PROFIT_MACHINE_TYPE_B * numMachinesTypeB); int futureWeeksProfit = maxProfits[numWeeks - 1][numMachinesRemainingTypeA + numMachinesRemainingTypeB]; int possibleProfit = currentWeekProfit + futureWeeksProfit; if (possibleProfit > maxProfit) { maxProfit = possibleProfit; } } maxProfits[currentWeek][currentMachines] = maxProfit; } } return maxProfits[numWeeks][numMachines]; } } Java code (Top-down approach [memoization]) import java.util.Arrays; public class MachineMaxProfit { private static final int NOT_ASSIGNED = -1; private static final int PROFIT_MACHINE_TYPE_A = 300; private static final int PROFIT_MACHINE_TYPE_B = 500; private static final float PERCENTAGE_DIE_MACHINE_TYPE_A = 0.3f; private static final float PERCENTAGE_DIE_MACHINE_TYPE_B = 0.6f; public static void main(String[] args) { int weeks = 5; int numMachines = 10; int maxProfit = computeMaxProfit(weeks, numMachines); System.out.println("The maximum profit for " + numMachines + " machine(s) operating for " + weeks + " week(s) is " + maxProfit + "."); } public static int computeMaxProfit(int numWeeks, int numMachines) { int[][] maxProfits = new int[numWeeks + 1][numMachines + 1]; for (int week = 0; week <= numWeeks; ++week) { Arrays.fill(maxProfits[week], NOT_ASSIGNED); } return computeMaxProfit(numWeeks, numMachines, maxProfits); } private static int computeMaxProfit(int numWeeks, int numMachines, int[][] maxProfits) { if (numWeeks <= 0 || numMachines <= 0) { return 0; } if (maxProfits[numWeeks][numMachines] != NOT_ASSIGNED) { return maxProfits[numWeeks][numMachines]; } int maxProfit = 0; for (int numMachinesTypeA = 0; numMachinesTypeA <= numMachines; ++numMachinesTypeA) { int numMachinesTypeB = numMachines - numMachinesTypeA; int numMachinesRemainingTypeA = (int)Math.floor(numMachinesTypeA * (1 - PERCENTAGE_DIE_MACHINE_TYPE_A)); int numMachinesRemainingTypeB = (int)Math.floor(numMachinesTypeB * (1 - PERCENTAGE_DIE_MACHINE_TYPE_B)); int currentWeekProfit = (PROFIT_MACHINE_TYPE_A * numMachinesTypeA) + (PROFIT_MACHINE_TYPE_B * numMachinesTypeB); int futureWeeksProfit = computeMaxProfit(numWeeks - 1, numMachinesRemainingTypeA + numMachinesRemainingTypeB, maxProfits); int possibleProfit = currentWeekProfit + futureWeeksProfit; if (possibleProfit > maxProfit) { maxProfit = possibleProfit; } } maxProfits[numWeeks][numMachines] = maxProfit; return maxProfit; } } Sample output The maximum profit for 10 machine(s) operating for 5 week(s) is 7900. Press any key to continue . . .