PackageDelivery
SRM 363 · 2007-08-11 · by mateuszek
SRM 363 · 2007-08-11 · by mateuszek · Dynamic Programming
Problem Statement
Problem Statement
You have been assigned to deliver a number of packages from a warehouse to various destinations along a straight line. At the beginning, all the packages are at the warehouse, which is at the left end of the line. You and your truck are also at the warehouse.
Your truck has room for truckCapacity packages. Driving the truck costs fuelCost dollars per mile, regardless of the number of packages on the truck. You may park the truck anywhere you'd like, but each time you park somewhere other than at the warehouse, it costs parkingCost dollars. The truck must always be parked while you deliver a package to its destination. In other words, you cannot drop packages from a moving truck. You may never leave packages anywhere other than at their destinations, at the warehouse, or in the truck.
You can also carry packages on foot, but you can only carry one package at a time. It costs walkCost dollars per mile to walk while carrying a package. Walking without carrying anything costs nothing.
You are given aint[] packages, each element of which is the distance (in miles) of a package's destination from the warehouse. You must deliver all the packages, but you do not have to return the truck to the warehouse. Return the minimal cost required to do this.
Your truck has room for truckCapacity packages. Driving the truck costs fuelCost dollars per mile, regardless of the number of packages on the truck. You may park the truck anywhere you'd like, but each time you park somewhere other than at the warehouse, it costs parkingCost dollars. The truck must always be parked while you deliver a package to its destination. In other words, you cannot drop packages from a moving truck. You may never leave packages anywhere other than at their destinations, at the warehouse, or in the truck.
You can also carry packages on foot, but you can only carry one package at a time. It costs walkCost dollars per mile to walk while carrying a package. Walking without carrying anything costs nothing.
You are given a
Constraints
- packages will contain between 1 and 50 elements, inclusive.
- Each element of packages will be between 1 and 1000000, inclusive.
- walkCost, fuelCost and parkingCost will each be between 0 and 1000000, inclusive.
- truckCapacity will be between 1 and 50, inclusive.
Examples
0)
{ 1, 2, 3 }
3
2
3
3
Returns: 13
One of the best possible ways is to load all packages onto the truck, then park it at point 2 and walk from there.
1)
{ 1, 2, 3, 4, 5 }
3
2
3
5
Returns: 23
Here, one of the best ways is to load all the packages onto the truck and then park it two times - first, at point 2, then, point 4.
2)
{ 1, 2, 3, 4, 5 }
11
5
9
2
Returns: 91
3)
{ 5, 5, 5 }
1
1
1
3
Returns: 6
Note that elements of packages don't have to be distinct.
4)
{ 52345, 745521, 75853, 758632, 968654, 86578, 3658, 86784, 867845, 968, 74567, 6457, 25896, 67869, 47756 ,856785, 87575, 36658, 47756, 4567 }
645746
88575
479887
11
Returns: 95080562653
Submissions are judged against all 95 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PackageDelivery with a public method long long minimalCost(vector<int> packages, int walkCost, int fuelCost, int parkingCost, int truckCapacity) · 95 test cases · 2 s / 256 MB per case