寻找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），但当然还有其他不同的组合需要您首先尝试。那么如何编写一个算法来查找此列表中的最佳价格呢？

谢谢！

- danielovich

---

http://en.wikipedia.org/wiki/Knapsack_problem - Andreas Brinck

第一次阅读时完全误解了你的问题...(后来：喝了点咖啡，理解得更好了！) 如果我的回答还没有被删除，请忽略它。 - Dan Tao

@danielovich：据我所知，这可以被准确地表述为“0-1背包问题”，它比一般的背包问题容易解决（您可以简单地用尽可能多的“一天”作为种子来填充您的“0-1背包”，半数的“两天”，三分之一的“三天”等等）。实际上，“0-1背包问题”有一个非常快速的精美“DP”解决方案。 - SyntaxT3rr0r

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

- IVlad

Answer 2

上面链接的维基页面显示这是一个 NP 完全问题，所以我想没有好的方法来解决它。 但是，如果你想强制求解，我建议先过滤掉“无用”的字段。

在你的例子中，通过一些简单的检查，你可以过滤掉 3 和 4，因为它们总是可以被 1+2 和 2+2 覆盖。(你也可以用蛮力法做到这一点)

然后，你应该只剩下了 3 种组合可供选择，如果你是为租车公司或酒店编写程序，这应该不会太糟糕……

(如果你想查找 30 天的最佳价格，最多只需要进行 30 x 15 x 4 次操作，对于计算机来说并不是很大。)

嗨，WizardOfOdds：

我正在尝试学习如何将此问题作为 0-1 背包问题解决，但我有些困惑……

(你可以简单地用尽可能多的“一天”作为“0-1背包”，其次是一半数量的“两天”，三分之一的“三天”，等等)。

我应该理解为，如果我们想要找到7天的解决方案，那么我们可以考虑：

7 x 1天 0/1？

3 x 2天 0/1？

2 x 3天 0/1？

1 x 4天 0/1？

我猜，我真的不明白为什么会有这么多“一天”，“半天”，“三分之一”等。

- user227353

---

对我来说，这相当于一个0-1背包问题，它有一个已知的DP解决方案非常高效。 不需要在这里使用暴力方法，也不需要考虑它是NP完全背包问题。 我相信这等价于“0-1背包问题”：因此，有一个已知的DP（动态规划）解决方案可用于大多数输入（如果它不适用于OP的数据[因为他们会使用巨大的数字，使得确切的DP算法不合适，这是非常不可能的]然后你可以找到一个近似值，你可以证明它至少是最佳答案的 'x' 百分比。 - SyntaxT3rr0r

Answer 3

虽然基本上这是背包问题，但您可能可以进行一些简单的分析，以过滤掉不好的决策（在您的例子中，是3天和4天的预订套餐）。

首先，我会根据天数和每日平均价格对列表进行排序。在您的例子中，这将产生以下结果...

天数    平均价
----    -------
1       1000
2       600
3       833
4       775
7       571

然后，我会过滤掉所有在遍历此列表时增加的值。一个简单的假设是，如果较短停留时间的平均值增加，则使用X个较短的停留时间的总和可能会获得更好的费率（显然并非始终如此 - 如果将1天的费率设置为1301，则3天的费率将变得更好，但4天的费率仍然很糟糕 - 尽管在您的示例中确实有效）。更详细的分析将其转化为背包问题。

天数    平均价
----    -------
1       1000
2       600
3       833      已删除
4       775      已删除
7       571

现在，在建立预订时，按照天数降序排序，并通过从所需天数中减去最大可能的预订来建立总预订，直到填满为止。因此，一个11天的预订将是一个7天和两个2天；一个10天的预订将是一个7天、一个2天和一个1天。

- Austin Salonen