I need help with number 3 For each of the following problems give: A. The functi

Question

I need help with number 3

For each of the following problems give: A. The function that represents the quantity to be optimized. This includes specifying the parameters. E.g. F(I, J): this represents the maximum number of coins that the robot can pick up from a rectangle of size IxJ made up of the first I rows and first J columns.. B. The recurrence formula: the formula that specifies the recurrence relation that represents the relationship between larger problems and smaller problems. E.g. for the robot problem F(l, J):- max {F(l, J), F(I, J)} + 6 i j where 5 i, j - 1 if there is a coin in the i j square and 0 if not C. The base cases: E.g. F(0, J)- F(I, 0) _ 0 for all I from 0 to N and all J from 0 to M D. The final solution: E.g. F(N, M) if the original problem is stated as an N times M board E. The pseudo code for the iterative algorithm to fill in a table that would be used for a bottom up dynamic programming solution 1. Given an unlimited supply of coins of denominations 1 -d_1

Explanation / Answer

mile[] = {} // distance in miles in increasing order
profit[] = {} // profit earned if restaurent is opened at respective position
maxprofit[] = {0} // maxprofit upto i;
result = profit[0];
for i = 0 to mile.size()
   maxprofit[i] = profit[i] // by default maxprofit at location i is profit[i]
   for j = 0 to i
       if (mile[i] - mile[j] > k && maxprofit[j] + profit[i] > maxprofit[i])
       // if distance between mile[i] - mile[j] > k and we are making profit by having a site at i, add this to our result
           maxprofit[i] = maxprofit[j] + profit[i]
       result = max(result, maxprofit[i]) // update result in each iteration
print result

  
// code
int maxiprofit( int mile[], int profit[], int k, int n) {
   int maxprofit[n] = {0}
   int result = profit[0];
   for (int i = 0; i < n; i++) {
       maxprofit[i] = profit[i];
           for (int j = 0; j < i; j++) {
               if (mile[i] - mile[j] > k && maxprofit[j] + profit[i] > maxprofit[i])
                   maxprofit[i] = maxprofit[j] + profit[i];
           result = result > maxprofit[i] ? result : maxprofit[i]; // update result in each iteration
   return result;
}

complexity: O(N^2)

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.