Problem Statement in English

You’re given a 2D integer array items where items[i] = [fi, ci] indicates that the i-th item has a price of ci and a factor of fi. You’re also given an integer budget.

When you buy an item for the first time you also receive a free copy of each item j where fj is a factor of fi. You can buy the same item multiple times, but you can only receive the free copies of the items the first time you buy it.

You can receive the same item multiple times as a free copy if you buy multiple different items that have it as a factor.

Return the maximum number of items you can buy with the given budget.

Approach

The twist to this knapsack problem is that when we buy an item for the first time, we also receive free copies of items that are factors of it. This means that we just need to a step for the first time we buy an item, and another step for subsequent times we buy the item.

First off, let’s calculate the bonus for each item, which is the number of free items we get when we buy it for the first time. We can do this by iterating through the items and counting how many items are factors of it. Pretty vanilla.

Then, we can use a dp array to keep track of the maximum number of items we can buy with a given budget. Note that the overlapping subproblem here is that given a certain budget b, and current item c, our solution depends on the number of items we can buy for b - c.

To make things easier for ourself we try starting from each item.

For each item, we have three options: we can buy it for the first time, which gives us 1 + bonus[i] items, or we can buy it again, which gives us 1 item, or we have a better existing solution and we just use that.

Since our solution depends on the previous state of the dp array, we need to create a new dp array for the item we’re currently considering as the one we start from - let’s call it ndp. We will update this new dp array based on the current item and the previous dp array. Once we’re done with the current item, we will update our main dp array dp to be the contents of ndp.

The number of states in the dp array is budget + 1, since we want to consider all budgets from 0 to budget. For each item, we will iterate through all possible budgets from the cost of the item to the total budget (because to buy the item, we need at least its cost and can have a max budget of the total budget stated by the problem).

For each item, we will iterate through all possible budgets from the cost of the item to the total budget (because to buy the item, we need at least its cost and can have a max budget of the total budget stated by the problem).

  • For the first time we buy the item, the answer is dp[b - cost] + 1 + bonus[i], because we get the item itself and the bonus items, and we need to use the previous dp array dp (the overlapping subproblem we talked about) because we don’t want to include the updates we make for the current item from the same iteration. It has to be built on the previous state of the dp array, which is why we use dp and not ndp.

  • For subsequent times we buy the item, the answer is ndp[b - cost] + 1, because we only get the item itself, and we need to use the updated dp array ndp because we might have already bought the item for the first time and received the bonus items.

Once we’re done iterating through all the items and updating our ndp array, we can now update our main dp array dp to be the contents of ndp.

Once we’re done doing this for each item, our answer will be the maximum value in the dp array, which represents the maximum number of items we can buy with the given budget.

The reason we can’t assume that the greatest budget will always be the final answer is because of the bonuses we get from buying items for the first time. It’s possible that we can buy a certain item for the first time with a smaller budget and get a lot of bonus items, which allows us to buy more items overall than if we had a larger budget and didn’t buy things that gave as many bonus items.

And we’re done!

Solution in Python


class Solution:
    def maximumSaleItems(self, items: List[List[int]], budget: int) -> int:
        n = len(items)
        bonus = [0] * n

        for i in range(n):
            fi = items[i][0]
            for j in range(n):
                if i != j and items[j][0] % fi == 0:
                    bonus[i] += 1

        dp = [0] * (budget + 1)

        for i in range(n):
            cost = items[i][1]
            first = 1 + bonus[i]

            ndp = dp[:]

            for b in range(cost, budget + 1):
                ndp[b] = max(ndp[b], dp[b - cost] + first)

            for b in range(cost, budget + 1):
                ndp[b] = max(ndp[b], ndp[b - cost] + 1)

            dp = ndp

        return max(dp)

Complexity

  • Time: $O(n \times budget)$
    Since we have a nested loop where the outer loop iterates through the items and the inner loop iterates through the budget.

  • Space: $O(budget)$
    Since we are using a dp array of size budget + 1 to store the maximum number of items we can buy for each budget.

Mistakes I Made

I had to look this up :(

And we are done.