Consider the following inventory problem You are running a c

Consider the following inventory problem. You are running a company that sells some large product (lets assume you sell trucks), and predictions tell you the quantity of sales to expect over the next n months. Let d_i denote the number of sales you expect in month i. Well assume that all sales happen at the beginning of the month, and trucks that are not sold are stored until the beginning of the next month. You can store at most S trucks, and it costs C to store a single truck for a month. You receive shipments of trucks by placing orders for them, and there is a fixed ordering fee of K each time you place an order (regardless of the number of trucks you order). You start out with no trucks. The problem is to design an algorithm that decides how to place orders so that you satisfy all the demands {d_i}, and minimize the costs. In summary: There are two parts to the cost: (1) storage-it costs C for every truck on hand that is not needed that month; (2) ordering fees-it costs K for every order placed. In each month you need enough trucks to satisfy the demand d_j, but the number left over after satisfying the demand for the month should not exceed the inventory limit S. Give an algorithm that solves this problem in time that is polynomial in n and S.

Solution

Now I have written the code to make your understanding better. if you have any doubt or I have made a mistake you can ask me.

i/p

5 1 3
2 10 9 5 1
4

o/p
13

check if o/p is correct or not

1st month = 3(k cost)

2nd month = 1st month + 3 = 6 as left over can not be equal to 10 so it will waste to use storage

3rd month = above reason = 9

4th month = 12

5th month = 12 + 1(left over from previous month)

i/p

5 1 3
2 7 6 2 1
20

o/p
13

Check it with pencil and paper. Hint- only last two months you can use left overs otherwise the cost of storage will be higher than buying trucks