Find cheapest price for X number of days

I have a technical challenge for you regarding an algorithm.

Lets say I have this list of days and prices:

        List<ReservationPrice> prices = new List<ReservationPrice>();
        prices.Add(new ReservationPrice { NumberOfDays = 1, Price = 1000 });
        prices.开发者_StackOverflowAdd(new ReservationPrice { NumberOfDays = 2, Price = 1200 });
        prices.Add(new ReservationPrice { NumberOfDays = 3, Price = 2500 });
        prices.Add(new ReservationPrice { NumberOfDays = 4, Price = 3100 });
        prices.Add(new ReservationPrice { NumberOfDays = 7, Price = 4000 });

What I would like to able to do now is:

give me the best price from the list based on a number of days.

So if ask for 3 days the best price from the list is from child one (1000) and two (1200), but there are of course different combinations you would have to try out at first. How would an algorithm that found the best price from this list look like ?

Thank you!

---

It's similar to the subset sum problem.

Here's an algorithm in pseudocode first:

Let S[i] = minimum sum obtainable for days = i, initialized to infinite at first
S[0] = 0
for (int i = 0; i < prices.Count; ++i)
{
    for (int j = MAX_DAYS; j >= prices[i].days; --j)
        S[j] = min(S[j], S[j - prices[i].days] + prices[i].price);
}

Then use S to answer each query. Here it is in C#. There is room for improvement of course.

class Program
{
    static void Main()
    {
        List<ReservationPrice> prices = new List<ReservationPrice>();
        prices.Add(new ReservationPrice { NumberOfDays = 1, Price = 1000 });
        prices.Add(new ReservationPrice { NumberOfDays = 2, Price = 1200 });
        prices.Add(new ReservationPrice { NumberOfDays = 3, Price = 2500 });
        prices.Add(new ReservationPrice { NumberOfDays = 4, Price = 3100 });
        prices.Add(new ReservationPrice { NumberOfDays = 7, Price = 4000 });

        DaysMinSum.Precompute(prices);
        Console.WriteLine(DaysMinSum.GetAnswer(5));
        Console.WriteLine(DaysMinSum.GetAnswer(4));
        Console.WriteLine(DaysMinSum.GetAnswer(7));
        Console.WriteLine(DaysMinSum.GetAnswer(6));
        Console.WriteLine(DaysMinSum.GetAnswer(100));
        Console.WriteLine(DaysMinSum.GetAnswer(3));
    }
}

static class DaysMinSum
{
    private static Dictionary<int, int> S = new Dictionary<int, int>();

    public static int GetAnswer(int numDays)
    {
        if (S.ContainsKey(numDays))
        {
            return S[numDays];
        }
        else
        {
            return -1;
        }
    }

    public static void Precompute(List<ReservationPrice> prices)
    {
        S.Clear();
        int maxDays = 0;

        for (int i = 0; i < prices.Count; ++i)
        {
            maxDays += prices[i].NumberOfDays;
        }

        for (int i = 0; i <= maxDays; ++i)
        {
            S.Add(i, 1 << 30);
        }

        S[0] = 0;
        for (int i = 0; i < prices.Count; ++i)
        {
            for (int j = maxDays; j >= prices[i].NumberOfDays; --j)
            {
                S[j] = Math.Min(S[j], S[j - prices[i].NumberOfDays] + prices[i].Price);
            }
        }
    }
}

class ReservationPrice
{
    public int NumberOfDays { get; set; }
    public int Price { get; set; }
}

---

While this basically is the knapsack problem, you may be able to do some simple analysis to filter out poor decisions (in your example, the 3- and 4-day reservation packages).

First of all, I would sort the list by the number of days and the average per day price. In your example, this would yield...

Days    Average
----    -------
1       1000
2       600
3       833
4       775
7       571

Then I would filter out all the values that increase as you traverse this list. A simple hypothesis could be that a day with increased average from a shorter stay can have a better rate by using the sum of X shorter stays (obviously not true all of the time -- set the 1-day rate 1301 and the 3-day rate becomes better but the 4-day rate is still bad -- though it does work in your example). More detailed analysis turns this into the knapsack problem.

Days    Average
----    -------
1       1000
2       600
3       833      removed
4       775      removed
7       571

Now when building up reservation, sort by the number of days descending an build up the total reservation by subtracting the largest possible reservation from the desired day count until you've filled it. So an 11-day reservation would be a 7-day and two 2-days; a 10-day would be a 7-day, a 2-day, and a 1-day.

---

That wiki page linked above says it's a np complete problem, so I guess there is no good way to solve it. But, if you want to brute force it, I would suggest to filter out the 'useless' fields first.

In your example, with some simple check you can filter out 3 and 4 because they can always overwrite by 1+2 and 2+2. (you can do this with brute force too)

Then, you should only have 3 combination left to choose, which shouldn't be too bad if you making the program for a rental company or hotel...

( if you want to check out best price for 30 days, it should only take max 30 x 15 x 4 operations, which isn't that large at all for a computer to calculate.)

Hi WizardOfOdds:

I am trying to learn how to solve this problem as 0-1 Knapsack, and I'm kind confused...

(you can simply 'seed' your "0-1 Knapsack" with as many 'one day' as the maximum you want to find, half as many 'two days', one third as many 'three days', etc.).

Should I understand that as if we want to find a solution for 7 days, then we think as :

7 x 1 day 0/1?

3x 2 day 0/1?

2x 3 day 0/1?

1x 4 day 0/1?

I guess, I really don't get what/why is the

as many 'one day', 'half', 'third'...