Exercise Session 3: Dynamic Programming

Reminders

• Course Session 3 (in French)
• How to submit your work
• Deadline for submission: tonight at 23h59.
• To run the tests : download test.tar.gz and unpack it in your work directory

Exercise 1: Land plots

1. A farmer owns a very long field of Nx1 square land plots put alongside each other, and numbered 0, ..., N-1.
   Each land plot (aka "parcel") is special in its own way. The farmer estimates that growing corn on plot #i will earn him Profit[i].
   There is a constraint: because corn is such a demanding crop, the farmer can never grow corn on two adjacent plots.
   How can the farmer maximize profit (aka "gain")?
   
   Implement in a new file parcel.cc the function MaxGain() described in file parcel.h:

   #ifndef __PARCEL_H
   #define __PARCEL_H
   
   #include <vector>
   using namespace std;
   
   // The profit (aka "Gain") from growing corn on plot #i (i.e. using it) is gain[i].
   // If plot #i is used, then plots #i-1 and #i+1 cannot be used (if they exist).
   // This function returns the maximum possible profit from using plots.
   //
   // EXAMPLE:
   // MaxGain([3, 7, 2, 1, 8, 4, 3]) = 18
   int MaxGain(const vector<int>& gain);
   
   #endif  // __PARCEL_H

   One may use the recursive approach with memoization (for example with an auxiliary function MaxGainAux() that would take as extra argument a memoization array, and an index indicating the already-explored part of the plots array), or the iterative approach.
   
   Test:

   rm test.tar.gz; wget --no-cache http://fabien.viger.free.fr/oc/td3/test.tar.gz
   tar xf test.tar.gz
   make parcel

   TO SUBMIT: parcel.cc
   
   
2. Explain in a new file parcel.txt the time and space complexity of your algorithm.
   If you figure it out, also explain how one could use only O(1) space (not counting the inputs) without increasing the time complexity.
   
   
3. Implement in a new file parcel2.cc the function OptimalParcels() described in file parcel2.h:

   #ifndef __PARCEL2_H
   #define __PARCEL2_H
   
   #include <vector>
   using namespace std;
   
   // This is the same problem as before, but instead of returning the maximum profit (aka
   // gain), we want to return the list of plots (aka parcels) to use to maximize profit.
   // The list must be sorted in ascending order.
   //
   // EXAMPLE:
   // OptimalParcels([3, 7, 2, 1, 8, 4, 3]) = [1, 4, 6] (indices of the chosen parcels)
   vector<int> OptimalParcels(const vector<int>& gain);
   
   #endif  // __PARCEL2_H

   Test: make parcel2
   
   TO SUBMIT: parcel2.cc
   
   

Exercise 2: Optimal Cut

1. You own a sawmill business, which produces wooden boards. To simplify, we'll assume that all boards have the same width and thickness: only their length differs.
   Your only client gave you a buy list of various cuts (i.e. lengths): for each length, they will buy any amount of board of that length that you can provide, and pay you a given price for each board of that length. The per-length price varies.
   Today, a tree trunk arrived in your factory, and you were able to produce one very long board of length L (which you can then re-cut in smaller boards).
   Your work is to determine how to cut this single board of length L in sellable boards, so as to maximize your total sell price.
   
   Implement in a new file cut.cc the function OptimalCut() described in file cut.h:

   #ifndef __CUT_H
   #define __CUT_H
   
   #include <vector>
   using namespace std;
   
   // Describes a particular 'cut' of a wooden board: its length and price.
   struct PricedCut {
     int length;  // Always >= 1.
     double price;  // Always > 0.
   };
   
   // Finds the optimal way to cut a board of length L into smaller, sellable
   // cuts, so as to maximize the total sale price.
   // Returns this maximum sale price.
   // Also outputs the list of chosen cuts (a given cut may be repeated several
   // times), in any order, in the vector "cut_indices": one will simply write
   // the indices of the cuts from the original "cuts" vector.
   //
   // IMPORTANT: The unit test of this function has 2 parts: first, it tests
   // the return value, then it tests the "cut_indices" output. If you don't
   // fill the latter, you may still score points.
   //
   // WARNING: prices are doubles (i.e. floating-point numbers), not integers.
   //
   // EXAMPLE:
   // OptimalCut(257, {{40, 3.8}, {70, 6.7}, {90, 9.0}}) = 6.7 + 9.0 + 9.0
   // avec cut_indices = [1,2,2]. 
   double OptimalCut(int L, const vector<PricedCut>& cuts,
                     vector<int>* cut_indices)
   
   #endif  // __CUT_H

   Test: make cut
   
   TO SUBMIT: cut.cc