❔ Dynamical Programming to find min cost of supplying cars for 'n' months.
Hello everyone, i got an assignment about dynamical programming implementation of a min. cost finding program. I did it without using DP but it doesn't check all cases i.e. it doesn't give the correct output for dif. values that may be given.
The question is:
* Use dynamical programming to find min. cost of providing demanded number of cars (demand={4,6,7,5} for example.) for n months.
Rules:
- We can provide/supply p cars each month.
- If demand is higher than p, we buy the car for cost of c or we use our cars from prev. months but we pay storage cost to do so.
- The storage cost is storage[0] for 1 car, storage[3] for 4 cars etc and are paid each month(0 for 0 cars obv.)
- and storage array has a size that is equal to total demand in all months because we'll account all cases.
- you don't have to put cars in storage if p exceeds demand for that year.
- storage, demand, p, c are given at the start of the code.
Ideally you'd choose to buy x cars (cost c) over storage(future use) if c is cheaper. But if the storage array has absurd values such as {5, 6, 1}, it may eventually be cheaper to use the car from previous year. So in that case all i can think is calculating every scenario possible and find the min cost?
I can't think how to even start with DP, will the array be 2D? What will the DP array's indexes represent? I'd appreciate any help, thanks!
15 Replies
Do a recursive solution, then implement memoization. See what data structure happens to fit the recursive solution
I tried to change the knapsack problem code to fit this but this one is more complex, i'm stuck on DP array to start :/
sounds like youre trying to force an array as a solution. first figure out a solution
dynamical programming has to use an array no?
nit: the term is 'dynamic programming'
It needs a recursive structure, or for something like p(x+y) = p(x) + p(y) to hold true
i mean i kinda get the knapsack problem using DP but the array indexes are weight and item but in my case demand varies so i'm confused as to what the indexes should represent. month and demand? and how does storage fit into the recursion?
storage is just part of the cost.
purchases + storage fees are the total cost, right?
yes
but i can't see it so simple, i don't think it can be formulated by a few comparisons/ 'cost this way is cheaper for this month so we should choose this one'.
That's the point of dp + divide/conquer. you brute force it
ok thank you i will try it with recursion
nope, can't bruteforce when there's storage costs that carry over from previous months
sounds like an extra parameter
what would the array be for bruteforce? dp[n] or dp[totalDemand] i'm confused about DP still :/
if you can't figure out an efficient storage structure, just use a dictionary
with all parameters as keys
In a tuple, that is
I doubt bruteforce is what i should do though because with one decision of not storing/storing a car entire thing changes so the previous values are useless that is the entire point of dynamic programming.
I constantly keep getting back to the beginning, deciding to use memoization, recurrence? i hate having to use a specific thing. I tried a lot of things but in the end with change of parameters answers were wrong. I think i will give up, thank you both for the help.
Was this issue resolved? If so, run
/close - otherwise I will mark this as stale and this post will be archived until there is new activity.