A company called Wonderland offers several types of parking permits to its emplo

Question

A company called Wonderland offers several types of parking permits to its employees, with different durations and prices. The co-op student Alice will work in Wonderland for n consecutive days. She wants to figure out the cheapest collection of parking permits that would cover all days she needs to be present at work. Alice can buy as many permits of a given type as she likes. Let's assume there are k type of permits 1, elementof, k: the price of permit type t is p_t dollars and duration d_t. Alice needs to stay at work on n consecutive days. Our goal is to help Alice figure out how to park for all n days as cheaply as possible. Assume we're only interested in the optimal cost for parking over n days. Assume the durations of each of the k permits are stored in the array D and the prices are stored in the array P. Give a recurrence C(n) that describes the optimal cost to park for n > 0 days, in terms of the optimal cost to park for some smaller number(s) of days. Give the corresponding base case(s) for your recurrence. Assuming k (the number of types of permits) is a constant, design a linear-time algorithm to compute the optimal parking cost by converting your recurrence relation above into a memorized or dynamic programming solution.

Explanation / Answer

1) C(n) = 0 if n = 0; else min(C(n), C(n - D[i] + P[i]) where 0 <= i < k
2) base case C[0] = 0;
3)

Given :
   D = Duration in Day for permit
   P = Price of permit type corresponding to D
   n = No. of day for which permit is required
   k = size of D

Required:
   minimum cost for n day permit
  
Declare C[n + 1] // C[i] represent cost of premit for i day.

for (i = 0; i <= n; i++) C[i] = INT_MAX;
C[0] = 0;

for (int i = 0; i < k; i++) {
   for (int j = D[i]; j <= n; j++) {
       C[j] = min (C[j], C[j - D[i]] + P[i])
   }
}
minimal_cost = C[n]

C++ code RUN

#include <iostream>
#include <vector>
using namespace std;

int mac(vector<int> D, vector<int> P, int n)
{
    vector<int> C (n + 1, 0);
    for (int i = 0; i <= n; i++) C[i] = INT_MAX;
    C[0] = 0;

    for (int i = 0; i < D.size(); i++) {
        for (int j = D[i]; j <= n; j++) {
            C[j] = min (C[j], C[j - D[i]] + P[i]);
        }
    }
    return C[n];
}

int main()
{
    vector<int> D = {1, 2, 3, 4, 5} ;
    vector<int> P = {20, 30, 40, 100, 155};
    cout << mac(D, P,10);
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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