Welcome to Subscribe On Youtube

3946. Maximum Number of Items From Sale I

Description

You are given a 2D integer array items, where items[i] = [factori, pricei] represents the ith item. You are also given an integer budget.

There are unlimited copies of each item available for purchase.You may buy any number of copies of any items such that the total cost of the purchased copies is at most budget.

After buying items, you may receive free copies according to the following rules:

  • For each item i that you bought at least one copy of, you receive one free copy of every item j such that j != i and factori divides factorj.
  • Buying multiple copies of the same item i does not give additional free copies through item i.
  • The same item j can be received multiple times for free if it is received from purchases of different item types.

Return the maximum total number of item copies you can obtain, including both purchased copies and free copies, while spending at most budget on purchased items.

 

Example 1:

Input: items = [[6,2],[2,6],[3,4]], budget = 9

Output: 4

Explanation:

  • You can buy 2 copies of item 0 and 1 copy of item 2 for a total cost of 2 * 2 + 4 = 8, which is not greater than budget = 9.
  • Buying item 2 gives 1 free copy of item 0, because factor2 = 3 divides factor0 = 6.
  • You leave with 3 purchased copies and 1 free copy, for a total of 4 item copies.

Example 2:

Input: items = [[2,4],[3,2],[4,1],[6,4],[12,4]], budget = 8

Output: 10

Explanation:

  • You can buy 1 copy of item 0, 1 copy of item 1, and 2 copies of item 2 for a total cost of 4 + 2 + 2 * 1 = 8.
  • Buying item 0 gives 1 free copy of items 2, 3, and 4.
  • Buying item 1 gives 1 free copy of items 3 and 4.
  • Buying item 2 gives 1 free copy of item 4.
  • Thus, you receive 6 free copies. You leave with 4 purchased copies and 6 free copies, for a total of 10 item copies.

 

Constraints:

  • 1 <= items.length <= 1000
  • items[i] = [factori, pricei]
  • 1 <= factori, pricei <= 1500
  • 1 <= budget <= 1500

Solutions

Solution 1: Dynamic Programming (0-1 Knapsack)

Since buying the first item of a type is special and yields free items, we consider the first purchased item separately from the later purchases.

For the first purchased item, suppose we spend a budget of $i$ and obtain $f[i]$ items in total, including both the purchased item and the free items. For the later purchases, we can use the remaining budget $\text{budget} - i$ to buy the cheapest item, obtaining $\lfloor \frac{\text{budget} - i}{\text{mn}} \rfloor$ items, where $\text{mn}$ is the minimum price among all items. Therefore, we enumerate the budget $i$ spent on the first purchase and compute the maximum value of $f[i] + \lfloor \frac{\text{budget} - i}{\text{mn}} \rfloor$, which is the final answer.

The time complexity is $O(n^2 + n \times m)$, where $n$ is the number of items and $m$ is the budget.

  • class Solution {
    public int maximumSaleItems(int[][] items, int budget) {
        int[] f = new int[budget + 1];
        int mn = Integer.MAX_VALUE;

        for (int[] item : items) {
            int factor = item[0];
            int price = item[1];

            mn = Math.min(mn, price);

            int cnt = 0;
            for (int[] jItem : items) {
                if (jItem[0] % factor == 0) {
                    cnt++;
                }
            }

            for (int j = budget; j >= price; j--) {
                f[j] = Math.max(f[j], f[j - price] + cnt);
            }
        }

        int ans = 0;
        for (int i = 0; i <= budget; i++) {
            ans = Math.max(ans, f[i] + (budget - i) / mn);
        }

        return ans;
    }
}

  • class Solution {
public:
    int maximumSaleItems(vector<vector<int>>& items, int budget) {
        vector<int> f(budget + 1, 0);
        int mn = INT_MAX;

        for (const auto& item : items) {
            int factor = item[0];
            int price = item[1];

            mn = min(mn, price);

            int cnt = 0;
            for (const auto& jItem : items) {
                if (jItem[0] % factor == 0) {
                    cnt++;
                }
            }

            for (int j = budget; j >= price; --j) {
                f[j] = max(f[j], f[j - price] + cnt);
            }
        }

        int ans = 0;
        for (int i = 0; i <= budget; ++i) {
            ans = max(ans, f[i] + (budget - i) / mn);
        }

        return ans;
    }
};

  • class Solution:
    def maximumSaleItems(self, items: List[List[int]], budget: int) -> int:
        f = [0] * (budget + 1)
        mn = inf
        for factor, price in items:
            mn = min(mn, price)
            cnt = sum(factor_j % factor == 0 for factor_j, _ in items)
            for j in range(budget, price - 1, -1):
                f[j] = max(f[j], f[j - price] + cnt)
        return max(x + (budget - i) // mn for i, x in enumerate(f))


  • func maximumSaleItems(items [][]int, budget int) int {
	f := make([]int, budget+1)
	mn := math.MaxInt32

	for _, item := range items {
		factor := item[0]
		price := item[1]
		mn = min(mn, price)

		cnt := 0
		for _, jItem := range items {
			if jItem[0]%factor == 0 {
				cnt++
			}
		}

		for j := budget; j >= price; j-- {
			if f[j-price]+cnt > f[j] {
				f[j] = f[j-price] + cnt
			}
		}
	}

	ans := 0
	for i, x := range f {
		extra := (budget - i) / mn
		ans = max(ans, x+extra)
	}

	return ans
}

  • function maximumSaleItems(items: number[][], budget: number): number {
    const f: number[] = new Array(budget + 1).fill(0);
    let mn: number = Infinity;

    for (const [factor, price] of items) {
        mn = Math.min(mn, price);

        let cnt = 0;
        for (const [factor_j, _] of items) {
            if (factor_j % factor === 0) {
                cnt++;
            }
        }

        for (let j = budget; j >= price; j--) {
            f[j] = Math.max(f[j], f[j - price] + cnt);
        }
    }

    let ans = 0;
    for (let i = 0; i <= budget; i++) {
        ans = Math.max(ans, f[i] + Math.floor((budget - i) / mn));
    }

    return ans;
}

All Problems

All Solutions