Lift
Autumn Tournament (2015)
Submission name: lift.cpp
Problem summary
Four children must travel to their floor. The lift can carry at most M people and total weight at most N on each trip. Find the minimum number of trips required.
Input
M and N, followed by the four child weights.
Output
The minimum number of lift trips.
Constraints
2 ≤ M ≤ 100; 1 ≤ N ≤ 1000; each child weight is from 1 to N.
Worked example
Original statement sample.
Input
4 100 25 28 33 18
Output
2
Solution analysis
- Represent a group of children by a four-bit mask. Precompute its number of children and total weight; a group is allowed exactly when both lift limits are respected.
- Let dp[mask] be the minimum trips needed for the children in mask. Start with dp[0]=0. Try every nonempty allowed submask as the children riding on the final trip, giving dp[mask]=min(dp[mask],dp[mask without submask]+1).
- The sample weights sum to 104, so one trip is impossible despite the four-person limit. A group of three and the remaining child fit on two trips, so the answer is 2.
Why it works
Every valid final trip is an allowed subset, leaving the remaining children to earlier trips. The recurrence considers every such choice. Induction on the number of children proves the smaller state optimal and hence the full state optimal. Each child fits alone, so a solution always exists.
Watch out. Check both passenger count and weight. Greedy pairings need not solve general grouping constraints.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
using namespace std;
int main(){
int capacity,limit;
cin>>capacity>>limit;
int weight[4];
for(int&value:weight){
cin>>value;
}
bool allowed[16]={};
for(int mask=1;mask<16;++mask){
int count=0;
int total=0;
for(int i=0;i<4;++i){
if((mask&(1<<i))!=0){
++count;
total+=weight[i];
}
}
allowed[mask]=count<=capacity&&total<=limit;
}
int dp[16];
fill(dp,dp+16,5);
dp[0]=0;
for(int mask=1;mask<16;++mask){
// Enumerate the passengers of the last trip.
for(int trip=mask;trip!=0;trip=(trip-1)&mask){
if(allowed[trip]){
dp[mask]=min(dp[mask],dp[mask^trip]+1);
}
}
}
cout<<dp[15]<<'\n';
}