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

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

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

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

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

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

Привет WizardOfOdds:

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

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

Должен ли я понимаю, что так, как будто мы хотим найти решение в течение 7 дней, то мы думаем, как:

7 х 1 день 0/1?

3 раза 2 день 0/1?

2 раза 3 дня 0/1?

1x 4 день 0/1?

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

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

Answer 2

Это похоже на subset sum problem.

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

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 3

Хотя это в основном проблема ранца, вы можете быть в состоянии сделать некоторый простой анализ, чтобы отфильтровать плохие решения (в вашем примере, 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-дневным.