Pack Grain Sacks by Value per Kilo
Solve this ProblemA trader has sacks of grain. Sack i is worth values[i] in total and weighs weights[i] kilos, and the truck can carry capacity kilos. Unlike an all-or-nothing load, any sack may be split: taking a fraction of a sack gives the same fraction of its value and weight. Find the maximum total value that fits, rounded down to a whole number.
Because sacks can be split, the best use of every kilo is the grain with the highest value per kilo. Ranking the sacks by that ratio and filling greedily — whole sacks first, then a fraction of the first one that doesn't fit — is optimal.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ values.length ≤ 12, and weights.length equals values.length - ◆
1 ≤ values[i] ≤ 100 and 1 ≤ weights[i] ≤ 50; sack i is worth values[i] in total and weighs weights[i] kilos - ◆
1 ≤ capacity ≤ 300 kilos - ◆
Any sack may be split: taking a fraction f of sack i adds f × values[i] in value and f × weights[i] in weight - ◆
Return the maximum total value, rounded down to a whole number
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Every Set of Whole Sacks Plus One Partial
BruteA key fact about splittable items: an optimal packing never needs to split more than one sack. So enumerate every subset of sacks taken whole (a bitmask), skip the subsets that are too heavy, and for each remaining subset consider (a) stopping there, or (b) filling the leftover room with a fraction of one sack not in the subset. Values are rounded down at each fraction, and since rounding down never changes which total is largest, the maximum of these is the answer. It is correct but examines 2ⁿ subsets.
O(2ⁿ · n)O(1)1class Solution {
2 public int maxPackedValue(int[] values, int[] weights, int capacity) {
3 int n = values.length;
4 int best = 0;
5 for (int mask = 0; mask < (1 << n); mask++) {
6 int weight = 0, value = 0;
7 for (int i = 0; i < n; i++) {
8 if ((mask & (1 << i)) != 0) {
9 weight += weights[i];
10 value += values[i];
11 }
12 }
13 if (weight > capacity) continue;
14 best = Math.max(best, value);
15 int room = capacity - weight;
16 for (int j = 0; j < n; j++) {
17 if ((mask & (1 << j)) != 0) continue;
18 int part = values[j] * Math.min(room, weights[j]) / weights[j];
19 best = Math.max(best, value + part);
20 }
21 }
22 return best;
23 }
24}Optimal — Sort by Value per Kilo and Fill Greedily
OptimalEach kilo of capacity should hold the most valuable grain available, so rank the sacks by value per kilo, best first. (Compare two sacks exactly by cross-multiplying — values[a] × weights[b] against values[b] × weights[a] — rather than dividing, which avoids rounding errors.) Then walk down the ranking: take each sack whole while it fits; at the first sack that does not fit, take just the fraction that fills the remaining room, add its (rounded-down) value, and stop. Sorting dominates the cost.
O(n log n)O(n)1class Solution {
2 public int maxPackedValue(int[] values, int[] weights, int capacity) {
3 int n = values.length;
4 Integer[] order = new Integer[n];
5 for (int i = 0; i < n; i++) order[i] = i;
6 Arrays.sort(order, (a, b) -> Integer.compare(values[b] * weights[a], values[a] * weights[b]));
7 int total = 0, room = capacity;
8 for (int idx : order) {
9 if (room == 0) break;
10 if (weights[idx] <= room) {
11 total += values[idx];
12 room -= weights[idx];
13 } else {
14 total += values[idx] * room / weights[idx];
15 room = 0;
16 }
17 }
18 return total;
19 }
20}