Question#4 -- Maximum Profit
You own a small business which ships packages by airplane from Bogota Columbia to
Miami Florida. Your plane makes one round trip each day. For each 24-hour
delay in shipping, you lose 20 percent of your profit. You have one plane,
and the plane can hold a maximum of W pounds of cargo. Since your business
is good, you are not able to put all the packages that are to be shipped
on the plane each day.
In order to minimize your losses you load your plane with the most
profitable packages first, until you have loaded W pounds.
The packages are rated: Each package p weighs wp
pounds and has a value of vp dollars. Lucky for you that
the items in a package are individually wrapped into one-pound items,
and you can make smaller packages out of larger ones.
Making new mailing labels and rewrapping is no problemo, compared to
the 20 percent loss if the package does not get shipped.
Input:
The first line specifies the maximum weight W that the plane can hold.
The rest of the lines specify each package: Each line specifies the weight
and cost for the package. All inputs are integers.
50
10 60
20 100
30 120
Output:
(1) The value of the cargo.
(2) For each package, how many of the individual items were shipped.
All outputs are also integers.
In the example above, the output is:
Value = 240
Package 1 = 10
Package 2 = 20
Package 3 = 20