Найти самую дешевую цену за Х дней

Question

У меня есть техническая проблема для вас относительно алгоритма.

Допустим, у меня есть этот список дней и цен:

        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 });

Что бы я хотел сейчас сделать, это:

дайте мне лучшую цену из списка на основе количества дней.

Так что, если спросить 3 дня, лучшая цена из списка - от ребенка один (1000) и два (1200), но, конечно, есть разные комбинации, которые вы должны попробовать вначале. Как будет выглядеть алгоритм, который нашел лучшую цену из этого списка?

Спасибо!

Answer 1

Это похоже на проблему подмножества сумм .

Вот алгоритм в псевдокоде сначала:

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);
}

Затем используйте S, чтобы ответить на каждый запрос. Вот это в C #. Конечно, есть место для улучшения.

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; }
}

Answer 2

Хотя это, в основном, проблема с рюкзаком, возможно, вам удастся провести простой анализ, чтобы отфильтровать неверные решения (в вашем примере - 3- и 4-дневные пакеты бронирования).

Прежде всего, я бы отсортировал список по количеству дней и средней цене за день. В вашем примере это даст ...

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

Тогда я бы отфильтровал все значения, которые увеличиваются при прохождении этого списка. Простая гипотеза может состоять в том, что день с увеличенным средним значением от более короткого пребывания может иметь лучшую скорость, если использовать сумму X более коротких пребываний (очевидно, не всегда верно - установите 1-дневную ставку 1301 и 3-дневную ставка становится лучше, но 4-дневная ставка все еще плоха - хотя она работает в вашем примере). Более подробный анализ превращает это в проблему ранца.

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

Теперь при создании резервирования сортируйте по количеству дней по убыванию, чтобы увеличить общее резервирование, вычитая максимально возможное резервирование из требуемого количества дней до тех пор, пока вы его не заполните. Таким образом, 11-дневное бронирование будет 7-дневным и двумя 2-дневными; 10 дней - это 7 дней, 2 дня и 1 день.

Answer 3

Эта вики-страница, указанная выше, говорит, что это полная проблема, так что я думаю, что нет хорошего способа ее решить. Но если вы хотите перебор, я бы предложил сначала отфильтровать «бесполезные» поля.

В вашем примере с помощью простой проверки вы можете отфильтровать 3 и 4, потому что они всегда могут перезаписать на 1 + 2 и 2 + 2. (вы можете сделать это также грубой силой)

Тогда вам нужно выбрать только 3 комбинации, что не должно быть плохо, если вы создаете программу для компании по прокату или отеля ...

(если вы хотите проверить лучшую цену в течение 30 дней, потребуется всего лишь 30 x 15 x 4 операций, что для компьютера не так уж и много.)

Привет WizardOfOdds:

Я пытаюсь научиться решать эту проблему, как 0-1 рюкзак, и я немного растерялся ...

(вы можете просто «затравить» свой «0-1» Рюкзак "с таким количеством" один день ", как максимум, который вы хотите найти, как половина много «двух дней», одна треть «три дня» и т. д.).

Если я пойму, что если мы хотим найти решение в течение 7 дней, тогда мы думаем как:

7 x 1 день 0/1?

3x 2 дня 0/1?

2x 3 дня 0/1?

1x 4 дня 0/1?

Полагаю, я действительно не понимаю, что / почему

столько «один день», «половина», «третий» ...