We are given an array of positive weights cost where cost[i] represents the cost of filling i + 1 kg’s of oranges in a bag (0-based indexing). We need to find the minimum cost to buy exactly w kg’s of oranges assuming infinite supply of each i + 1 kg’s of oranges.
I am having a hard time concluding the constraints in this problem because of which I am not able to identify the sub problems which we should solve to arrive at the solution of the final bigger problem.
Hence, after going through a dynamic programming question on SO, I tried to first implement the recursive brute force solution to get an idea of what are the smaller sub-problems.
def solve(n, cost, w, curr_cost, stack, dp):
if w < 0:
return
if w == 0:
print(stack, curr_cost)
res = min(res, curr_cost)
return
for i in range(n):
stack.append(i + 1)
solve(n, cost, w - (i + 1), curr_cost + cost[i], stack, dp)
stack.pop()
n = 5
cost = [20, 10, 4, 50, 100]
w = 5
res = math.inf
dp = [math.inf for _ in range(w + 1)]
solve(n, cost, w, 0, [], dp)
print(res)
Now, I am not able to memoize this solution. After memoization, I want to know how do we identify the constraints in a problem and how to use them to design a bottom-up approach. For example, if we make a 2D grid of dimensions n x w, we know for row 0 i.e., n=0, all the cells in that row will be cost[0] * w as we have packets of only 1kg of oranges. And for column $1$, all the cells in that column would be cost[0] as we need exactly 1kg of oranges which is possible only with packet of size 1kg. Now, how do I use this information to calculate values of other cells.
1 2 3 4 5 <- w
0 20 40 60 80 100
1 20 - - - -
2 20 - - - -
3 20 - - - -
4 20 - - - -
^n
i.e., writing the brute force recursive solution, identifying the smaller sub problems and then building up a bottom-up solution.
I have gone through various articles on the internet and SO but still not able to get an intuition of solving dynamic programming questions.