Dynamic Programming - Minimum cost to fill given weight in a bag

Question

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 an infinite supply of each i + 1 kg's of oranges.

How could we derive the sub-problems for this problem and how exactly in combination with those we get the solution to our final problem?

Hence, after going through a dynamic programming question on SO, I first tried to implement the recursive brute force solution to get an idea of what subproblems are we solving.

import math

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 cannot memoize this solution using which we can try to build a bottom-up solution. For example, if we make a 2D grid of dimensions n x w (after going through some hints), 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 a packet of size 1kg. Now, how do I use this information to calculate the 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 subproblems, and then building up a bottom-up solution and how exactly these subproblems combine that give us a final correct solution.

Answer 1

If I understand you correctly this problem is actually easily convertible to a shortest path problem. Each weight will be a node in the graph, with the desired weight being the target node. Then we can draw links between these nodes with the cost being the cost for the difference between these nodes. For example if the costs are [20, 10, 4, 50, 100], then the cost between node 20 and node 22, will be 10 (costs[1]). Then we can simply find the shortest path between node 0 and node w.

A python implementation could look like this:

import heapq

def calc(target_weight: int, weight_costs: list[int]):
    costs = [None] * (target_weight + 1)
    heap = []
    costs[0] = 0
    heapq.heappush(heap, (0, 0))
    while len(heap):
        cost, current_weight = heapq.heappop(heap)
        print(costs)
        if current_weight == target_weight:
            return cost
        for dw, dcost in enumerate(weight_costs, 1):
            ncost = cost + dcost
            nweight = current_weight + dw
            if nweight > target_weight:
                break
            if costs[nweight] is not None and costs[nweight] < ncost:
                continue
            costs[nweight] = ncost
            heapq.heappush(heap, (ncost, nweight))
    return -1

if __name__ == "__main__":
    target_weight = 5
    weight_costs = [20, 10, 4, 50, 100]
    print(calc(target_weight, weight_costs))

Answer 2

Let minCost[i] be the minimum cost to buy exactly i kilograms of oranges. The dynamic programming state here is the number of kilograms bought. The base case is minCost[0] = 0, i.e. it costs nothing to obtain 0 kilograms of oranges.

For the transition, we can consider all possible previous states that can reach the current state with a single transaction and take the minimum cost of all possible ways to reach this state.

def solve(n, cost, w):
    minCost = [0]
    for i in range(1, w + 1):
        minCost.append(min(minCost[i - j - 1] + cost[j]
                            for j in range(min(i, n))))
    return minCost[w]