BackhardGreedy

Maximizing Fractional Values Solution

Problem Statement

Given a set of items, each with a value and a weight, determine the subset of these items to include in a collection of limited capacity that maximizes the total value.

Example 1
Input
[{(value: 10, weight: 2)}, {(value: 5, weight: 1)}, {(value: 8, weight: 3)}], capacity = 4
Output
25.0

Explanation: Selecting the fraction with value 10 and weight 2, and then selecting a fraction of the item with value 5 and weight 1, to fill the remaining capacity, resulting in a total value of 10 + (2/2)*5 = 25.0/2 + 10 = 25.0

Example 2
Input
[{(value: 15, weight: 5)}, {(value: 20, weight: 10)}, {(value: 30, weight: 15)}], capacity = 12
Output
30.0

Explanation: Selecting the fraction with value 30 and weight 15, would exceed capacity, thus selecting the fraction with value 20 and weight 10, fills 10/12 of capacity, and then selecting a fraction of the item with value 15 and weight 5, to fill the remaining capacity, but that only fills 2/5 * 15 = 6, resulting in a total value of 20 + 10 = 30.0

Constraints

  • 1 ≤ number of items ≤ 100
  • 1 ≤ weight of each item ≤ 1000
  • 1 ≤ capacity ≤ 1000
  • All values and weights are non-negative integers

More Greedy Problems

Calculated Stack HorizoneasyCalculated Target IndexeasyCalculated 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