Thursday, August 14, 2014

MostProfitable

Problem:

TopCoder Problem Statement - MostProfitable

Overview:

Determine the most profitable item sold based on cost, price, and the number of sales.

Java Source:
01: /*
02: TopCoder
03: Single Round Match: 153
04: Division: 2
05: Level: 1
06: Points: 250
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1774
08:  */
09: 
10: public class MostProfitable {
11: 
12:     public String bestItem(int[] costs, int[] prices, int[] sales,
13:                            String[] items) {
14: 
15:         int maxProfitIdx = -1;
16:         int maxProfitAmt = Integer.MIN_VALUE;
17: 
18:         /*
19:          * For each item, calculate the profit.  If it's greater than any
20:          * we've seen so far, store that amount and its index.
21:          * The profit is calculated as the (price - cost) times the number of
22:          * sales.
23:          */
24:         for (int i = 0; i < costs.length; i++) {
25:             int profit = (prices[i] - costs[i]) * sales[i];
26:             if (profit > maxProfitAmt) {
27:                 maxProfitIdx = i;
28:                 maxProfitAmt = profit;
29:             }
30:         }
31: 
32:         /*
33:          * If the profit on our most profitable item is greater than 0,
34:          * return it's name.  If there are no profitable items,
35:          * return an empty string.
36:          */
37:         if (maxProfitAmt > 0) {
38:             return items[maxProfitIdx];
39:         } else {
40:             return "";
41:         }
42:     }
43: }
Notes:

There's just two steps to solving this problem. First, we need to loop through each item and calculate it's profit. This is given by the equation on line 25: profit = (prices[i] - costs[i]) * sales[i];

Then, for each profit, we need to determine if it's greater than any previously seen value; and if so, we store both the index of that item as well as the profit. This is done on lines 26-29. By requiring the new profit to be greater than maxProfitAmt (as opposed to greater than or equal to), we ensure that in cases of a tie, the first value remains.

No comments:

Post a Comment