PackageDelivery

SRM 363 · 2007-08-11 · by mateuszek

SRM 363 · 2007-08-11 · by mateuszek · Dynamic Programming

Show categories

Class Name: PackageDelivery

Return Type: long

Method Name: minimalCost

Arg Types: (vector<int>, int, int, int, int)

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 a int[] 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.

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.

Statement by TopCoder, Inc. — view the original on the archive.

Examples

{ 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, 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.

{ 1, 2, 3, 4, 5 }
11
5
9
2
Returns: 91

{ 5, 5, 5 }
1
1
1
3
Returns: 6

Note that elements of packages don't have to be distinct.

{ 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