Cargo in Order
National Olympiad — National round (2009 season)
Submission name: transport.cpp
Problem summary
A ship carries at most m tons per trip. Cargo items are indivisible and must be transported in their given order. Find the fewest trips needed to carry all items.
Input
n, then n positive item weights, then capacity m.
Output
The minimum number of trips.
Constraints
1 ≤ n < 1000; 0 < m < 10,000,000,000; each weight is below 1,000,000,000. The intended transportable instances require each item to fit in one trip.
Worked example
An independently prepared example for this explanation.
Input
3 20 35 10 50
Output
2
Solution analysis
- Fill each trip with the longest remaining prefix whose total weight does not exceed the capacity. When the next item would overflow the current load, start a new trip with that item.
- Because order is fixed, skipping an item to take a later one is forbidden. Leaving unused room when the next item fits cannot improve the number of trips.
- With weights 20, 35, 10 and capacity 50, the first trip carries 20. Adding 35 would exceed capacity. The second trip carries 35 + 10 = 45, so two trips suffice.
Why it works
The greedy first trip carries the longest feasible prefix. Any valid first trip ends no later. Extending it to the greedy endpoint only removes items from later trips and cannot increase their number. Repeating this exchange argument on the remaining suffix proves optimality.
Watch out. Preserve input order; this is not arbitrary bin packing. Use 64-bit capacity and sums. The statement does not specify an impossible-instance output.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> weights(n);
for (long long &weight : weights) {
cin >> weight;
}
long long capacity;
cin >> capacity;
int trips = 1;
long long load = 0;
for (long long weight : weights) {
// Take the longest remaining prefix that fits on this trip.
if (load + weight > capacity) {
trips++;
load = 0;
}
load += weight;
}
cout << trips << '\n';
}