[Guest]

You have $50 and a list of n food items, the list has the name of each item and beside it it's price and how many hours it will last when you eat it, you want to buy exactly 2 items that combined together will last the maximum number of hours while costing $50 or less...

The list you are given has the items ordered by price, how can you use that information to come up with an algorithm to find the best pair in O(n) time complexity (instead of O(n²))

[Guest]

the problem is a bit unclear do i only want to maximize hours, or find the best pair?

for example if there are 2 products which give me 100 hours but cost 50 dollars, while another pair gives me 99 hours but only costs 25 dollars, which one do you want?

[Guest]

then that's easy. go though the array looking for the price that's less than 25 but gives you the maximum number of hours.

then subtract that price from 50, start over, and find a price less then the new value that gives the maximum number of hours.

2n max time complexity.

[CaptainEd]

Anza Power, what if the best answer is a single product? For example, if the list is

$24, 10 hours

$24, 11 hours

$49, 50 hours,

the best combination would be the singleton for 50 hours, rather than the pair for 21.

Do you want the desired answer to be the pair for 21 hours?

If the list is

$1, 1

$24, 10

$24, 11

$49, 50

your algorithm finds the pair of $24s for 21 hours, and misses the other pair for 51 hours.

Edited September 9, 2011 by CaptainEd

[CaptainEd]

Add a few fields to the list item

hHSF ( the highest hours so far )

pHHSF ( the pointer to the item with highest hours so far)

pHWB ( the pointer to highest companion item that is within budget)

1) run through the list from low price to high price

----keep track of the highest hours so far (hHSF), and which item had it (pHHSF)

2) run through the list from ("this" from low price to high) and ("that" from high to low)

----keep track of the highest index of a companion item within budget (pHWB)--ie. where this.price + that.price <= 50

3) run through the list from low price to high price

----keep track of the highest hours for a pair (this.hHSF + this.pHWB.pHHSF) and its item numbers

(this, this.pHWB.pHHSF)

Edited September 9, 2011 by CaptainEd

[Guest]

Clarifications:

It doesn't matter the combined price of the pair, only that they cost less than $50...

We need exactly 2 items, if the number of items is variable then this problem becomes the Knapsack Problem, which is impossible to solve in less than exponential time...

CaptainEd: Your solution is a bit hard to understand, could you explain it in more common terms (i.e, Find the maximum hours, find the best companion for that maximum...etc)

Edited September 10, 2011 by Anza Power

[CaptainEd]

Sorry for the confusing description:

Assuming the list is sorted from low to high price, so, for example, the "last" one is the one with the highest price.

Point every item at the last one on the list that is a companion within budget. That is, if this one and that have total price <= $50, they are within budget. For example, if item 17 has price $22, and items 87, 88, and 89 have price $28, item 17 needs to point to 89.

For each item from the beginning to the end, note the record high hours up to and including the item, and the item that holds that record.

For example, if items 1,2,3,4 have hours 20, 10, 80, 5,

item 1 points to 1 (20 hours),

item 2 points to 1 (20 hours), because item 1 set a record that hasn't been beat yet.

item 3 points to 3 (80 hours), because item 3 sets a higher record.

item 4 points to 3 (80 hours). because item 3 still has the highest record so far.

item 2 does not point to 3, because no item can point to items beyond it in the list.

Now, run through the list, look at an item. find the one that has the highest (hours + companion's record hours).

Each of these activities can be done in linear time--find the last companion within budget, keep track of record hours so far, and look for the maximum pair value.

I hope that's better.

I figured out an answer to my question about the possibility of a single high-priced item. If we wanted to allow singleton solutions, we could simply start the list with an item with 0 price and 0 hours. Then a high-priced high-hour singleton could match with it.

Thanks for the puzzle, Anza Power!

Edited September 10, 2011 by CaptainEd