0

1 つは価格を表し、もう 1 つは単位数を表します。

例えば

decimal[] price = new decimal[] {1.65, 1.6, 1.55, 1.4, 1.3};
long[] quantity = new long[] {5000, 10000, 12000, 20000, 50000};

したがって、最初の 5000 ユニットはそれぞれ 1.65 の費用がかかり、次は 10000 の費用がかかり、それぞれ 1.6 の費用がかかります...

注文したい単位の量がわかっている場合、集計関数を使用して平均価格を取得するのは非常に簡単です。ユニットの合計金額が未知の変数である場合のアルゴリズムを考え出すのに苦労し、目標の平均価格が与えられました。

例: 平均単価 = 1.57 になるように注文する必要があるユニットの数

4

2 に答える 2

2

幾何学的に考えると、購入したアイテムの総数 (横軸) の関数として合計価格 (縦軸) を示すグラフを考えてみましょう。プロットは(0, 0)（ゼロを購入するとゼロの費用がかかります）で始まります。1.65まず、勾配と水平幅の直線セグメントを取得します5000。次に、その終点から、勾配1.6と幅の新しいセグメントが来10000ます。合計プロットは連続的で区分的に直線ですが、単価が変化する部分では曲がりがあります。

次に、問題を解決するには、方程式 の線y == 1.57 * x、つまり から始まり(0, 0)勾配 を持つ線との交点を見つけます1.57。セグメント (2 つのエンドポイントを知っている) ごとに、このセグメントが を満たしているかどうかを確認し、満たしy == 1.57 * xていれば、解決策があります。

price配列内の数値が減少している場合、最大で 1 つの解が存在する可能性があります (それ1.57が最初の価格 よりも厳密に小さい場合price[0])、プロットは凹関数を表します。

編集: C# でこのジオメトリをコーディングしようとしました。price私は、すべて正で減少している小切手を追加しませんでしたquantity。すべて正です。それを確認する必要があります。これが私のコードです：

        decimal[] price = { 1.65m, 1.6m, 1.55m, 1.4m, 1.3m, };
        long[] quantity = { 5000, 10000, 12000, 20000, 50000, };
        decimal desiredAverage = 1.57m;

        int length = price.Length;
        if (length != quantity.Length)
            throw new InvalidOperationException();

        var abscissaValues = new long[length + 1];
        var ordinateValues = new decimal[length + 1];
        for (int i = 1; i <= length; ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                abscissaValues[i] += quantity[j];
                ordinateValues[i] += price[j] * quantity[j];
            }
        } // calculation of plot complete

        int segmentNumber = Enumerable.Range(1, length).FirstOrDefault(i => ordinateValues[i] / abscissaValues[i] <= desiredAverage);
        if (segmentNumber > 1)
        {
            decimal x = (ordinateValues[segmentNumber - 1] * abscissaValues[segmentNumber] - abscissaValues[segmentNumber - 1] * ordinateValues[segmentNumber])
                / (desiredAverage * (abscissaValues[segmentNumber] - abscissaValues[segmentNumber - 1]) - (ordinateValues[segmentNumber] - ordinateValues[segmentNumber - 1]));
            Console.WriteLine("Found solution x == " + x);
        }
        else
        {
            Console.WriteLine("No solution");
        }

誰かがもっと美しく書けるかどうかはわかりませんが、うまくいくようです。出力は次のとおりです。

見つかった解 x == 29705.882352941176470588235294

于 2013-02-19T20:09:30.453 に答える
0

それは、1 つの答えが存在しないため、 1 つの平均をもたらす価格の1 つの組み合わせが存在しないためであると考えています。私たちが見ているのは、ナップザック問題の変種です。http://en.wikipedia.org/wiki/Knapsack_値の最大化ではなく最小化の問題。

編集: 以下で正しく指摘されているように、これはナップザックの問題の変種ではありません。閉じた形式のソリューションがあります：

T = 総購入数の場合、

1.57 = 1.55 * (12000/T) + 1.6 * ((T-12000)/T)。T について解きます。

開始価格ブロック (ここでは 1.55) は、問題で与えられた単位あたりの平均価格 (ここでは 1.57) のすぐ下のブロックです。

于 2013-02-19T19:22:56.410 に答える