Tap here to switch tabs
Problem
Submissions

Problem: Maximum Number of Items From Sale II

Maximum Number of Items From Sale II gives a budget and factor-price items. Maximize items within budget. Each purchase can add a different item whose factor is divisible by the purchased factor.

Statement

You are given an integer budget and a 2D integer array items, where items[i] = [factor_i, price_i] represents the factor and price of item i.

You can purchase any number of copies of each item as long as the total cost of all purchased items does not exceed budget.

For each purchased copy of item i, you receive one free copy of an item j (where j ≠ i) if factor_i divides factor_j. If no such item j exists, you do not receive a free copy for that purchased item.

Return the maximum total number of items, including both purchased and free copies, that you can obtain.

Constraints:

  • 1≤1 ≤ items.length ≤10⁵≤ 10⁵

  • items[i] = [factor_i, price_i]

  • 1≤1 ≤ factor_i ≤≤ items.length

  • 1≤1 ≤ price_i ≤10⁹≤ 10⁹

  • 1≤1 ≤ budget ≤10⁹≤ 10⁹

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Maximum Number of Items From Sale II

Maximum Number of Items From Sale II gives a budget and factor-price items. Maximize items within budget. Each purchase can add a different item whose factor is divisible by the purchased factor.

Statement

You are given an integer budget and a 2D integer array items, where items[i] = [factor_i, price_i] represents the factor and price of item i.

You can purchase any number of copies of each item as long as the total cost of all purchased items does not exceed budget.

For each purchased copy of item i, you receive one free copy of an item j (where j ≠ i) if factor_i divides factor_j. If no such item j exists, you do not receive a free copy for that purchased item.

Return the maximum total number of items, including both purchased and free copies, that you can obtain.

Constraints:

  • 1≤1 ≤ items.length ≤10⁵≤ 10⁵

  • items[i] = [factor_i, price_i]

  • 1≤1 ≤ factor_i ≤≤ items.length

  • 1≤1 ≤ price_i ≤10⁹≤ 10⁹

  • 1≤1 ≤ budget ≤10⁹≤ 10⁹