Can this problem be optimized with Dynamic Programming?

I have a problem that seems a dynamic programming one. I started learning about DP a few days ago and I'm stuck.

Definition

In a store, there are n items, each associated with two positive values a[i] and b[i]. There are infinitely many items of each type numbered from 1 to infinity and the item numbered j of type i costs a[i] + (j - 1) * b[i] units.

Determine the minimum possible cost to purchase exactly m items.

Constraints

1 <= n <= 10^5

1 <= a[i],b[i] <= 10^5

1 <= m <= 10^5

Example

Given n = 3, a = [2, 1, 1], b = [1, 2, 3], m = 4

The optimal types to buy are:

• Choose i = 1. This is the first purchase of this type of item, so j = 1.The first item costs a[1] + (1 - 1) * b[i] = 1 + (1 - 1) * 2 = 1.
• Choose i = 2. Again, it is the first purchase of this type so j = 1.The second item costs 1 + (1 - 1) * 3 = 1
• Choose i = 0 which costs 2 + (1 - 1) * 1 = 2
• When a second unit of any type is purchased, j = 2 for that transaction. The costs of a second units of each item are:

  • a[0] costs a[0] + (2 - 1) * b[0] = 2 + 1 * 1 = 3

  • a[1] costs 1 + 1 * 2 = 3

  • a[2] costs 1 + 1 * 3 = 4

  • Choose either a[0] or a[1] since they cost less.

The total cost to purchase is 1 + 1 + 2 + 3 = 7.

Function Description

The function getMinimumCost takes three parameters: a is a costs integer array, b is a costs integer array and m is the items to be purchased. It returns a long integer: the minimum cost.

This is my attempt so far:

from typing import List

class Solution: 
    def getMinimumCost(self, a: List[int], b: List[int], m : int):
        buyed_items = 0 
        minimum_cost = 0
        map_keys = [i  for i in range(len(a))]
        map_values = [0 for i in range(len(a))]
        items = dict(zip(map_keys, map_values))
        print(items)

        while buyed_items < m: 
            costs = [a[i] + (items[i] +1 - 1) * b[i]  for i in range(len(a)) ]
            costs.sort()
            for key in items:
                items[key] = items[key] + 1
            

            for cost in costs: 
                minimum_cost += cost 
                buyed_items += 1 

                if buyed_items == m:
                    break

        return minimum_cost

if __name__ == "__main__"   :
    sol = Solution()
    min_cost = sol.getMinimumCost([4, 1], [1, 3], 3)
    print("min cost to buy {} items is {}".format(3, min_cost))

The main issue in your attempt is that it takes one of each item type in each iteration of the outer loop, thereby taking an equal number of each until the required amount is reached, so that the final solution will have taken some 𝑘 items of type 1...𝑥 and (𝑘−1) of item types (𝑥+1)...𝑛. But the best solution could consist of taking completely different counts of items depending on the item type.

For instance, take this run:

a = [2, 10]
b = [2,  1]
min_cost = sol.getMinimumCost(a, b, 6)

The solution is to take 5 times the first item type (costs are 2, 4, 6, 8, 10) and once the second item type (cost is 10). The total minimal cost is then 40. Your code will return 45, because it takes 3 of each (costs are 2, 4, 6 for the first type, and 10, 11, 12 for the second).

Algorithm

No dynamic programming is needed.

I would suggest an algorithm where you only take one item per iteration of the outer loop, the cheapest one. To determine which is the cheapest one, sort is not very efficient, as that would have a time complexity of O(𝑛log𝑛) per call, giving a total time complexity of O(𝑚𝑛log𝑛).

It will be more efficient to maintain a min-heap populated with all item types, from which you extract the cheapest and push back that same item type with its updated price (so it can contend with the other prices). This pop/push operation has a time complexity of O(log𝑛), giving a total time complexity of O(𝑚log𝑛).

Implementation

from heapq import heapify, heapreplace

class Solution: 
    def getMinimumCost(self, a: List[int], b: List[int], m : int):
        priceheap = list(zip(a, b))  # (price, increase) tuples
        heapify(priceheap)  # from now on its a minheap

        minimum_cost = 0
        for _ in range(m):
            price, increase = priceheap[0]  # cheapest
            # increase price of the selected item for next time:
            heapreplace(priceheap, (price + increase, increase))
            minimum_cost += price

        return minimum_cost