This is a simple bin-packing problem with weights = 1
The solution is:
(1) sort the durations
3 3 3 6
(2) pack - starting with the small one to large -
as many as you can into T
|
cin >> T; // # mins (time)
cin >> C; // # chores
int t[C]; // Store times of each chore
for ( int i = 0; i < C; i++ )
cin >> t[i];
sort (&t[0], &t[C]); // Sort the times of chores from low to high
/* ================ Solve J4 =================== */
int k = 0; // # chores done so far
int sum = 0; // # minutes needed
while ( k < C && sum < T )
{ // Try to do the next chose
if ( sum + t[k] <= T )
{
sum += t[k];
k++;
}
else
break; // Out of time, done.
}
cout << "Answer: " << k << endl << endl;
|