BackhardGreedy

Optimized Subset Selection Solution

Problem Statement

Given a set of items, each with a value and a size, determine the optimal subset of these items to include in a collection of limited capacity, allowing for fractional parts of items to be selected, such that the total value of the selected items is maximized.

Example 1
Input
items = [(60, 10), (100, 20), (120, 30)], capacity = 50
Output
300.0

Explanation: Calculate value per unit for each item and sort, then select the highest value per unit items until capacity is full, allowing for fractions.

Example 2
Input
items = [(50, 5), (70, 10), (30, 15)], capacity = 15
Output
155.0

Explanation: Calculate value per unit for each item and sort, then select the highest value per unit items until capacity is full, allowing for fractions.

Constraints

  • 1 <= number of items <= 1000
  • 1 <= size and value of each item <= 10000
  • 1 <= capacity <= 10000
  • All sizes and values are integers

More Greedy Problems

Calculated Target IndexeasyCalculated Stack HorizoneasyCalculated Pointer AlignmenteasyNode Matrix Validator 3easy
View all problems →
Live Compiler
Loading...
Test Cases & Output
🔒 Sign up to run your code

🚀 Practice this problem

Run code, get AI hints & track streak

Sign Up Free