0

解決する必要があるのは次のとおりですが、これにアプローチする方法がわかりません。

隣接する駐車場があり、それらの配置は直線に似ています。各駐車場には値 (利益) が割り当てられています。必要な数のロットを購入できますが、それらは互いに隣接している必要があります (連続したセットで)。

入力(これは指定されています/入力するもの):

ロット数:9

各駐車場の値: 例: -5、0、7、-6、4、3、-5、0、2

表現 (見やすくするため) 各ボックスには、各ロットの利益が含まれています。

ここに画像の説明を入力

出力: 3 6 8 の意味: 3 - 開始ロット番号、6 - 終了ロット番号、8 - 総利益 (7 - 6 + 4 + 3)

複数の回答がある場合、プログラムは駐車場の数が最も少ないものを作成する必要があります。可能な答えがまだ複数ある場合、プログラムはそれらのいずれかを作成できます。

助けてください。前もって感謝します。

編集:私はそれを動作させました:

    /// <summary>
    /// The problem 2.
    /// </summary>
    public class MySuperAwesomeClass
    {
        #region Constants and Fields

        /// <summary>
        /// The seq end.
        /// </summary>
        private static int seqEnd = -1;

        /// <summary>
        /// The seq start.
        /// </summary>
        private static int seqStart;

        #endregion

        // Quadratic maximum contiguous subsequence sum algorithm.
        #region Public Methods and Operators

        /// <summary>
        /// The max sub sum 2.
        /// </summary>
        /// <param name="a">
        /// The a.
        /// </param>
        /// <returns>
        /// The max sub sum 2.
        /// </returns>
        public static int maxSumSub(int[] a)
        {
            int maxSum = 0;

            for (int i = 0; i < a.Length; i++)
            {
                int thisSum = 0;
                for (int j = i; j < a.Length; j++)
                {
                    thisSum += a[j];

                    if (thisSum > maxSum)
                    {
                        maxSum = thisSum;
                        seqStart = i;
                        seqEnd = j;
                    }
                }
            }

            return maxSum;
        }

        #endregion

        #region Methods

        /// <summary>
        /// The main.
        /// </summary>
        private static void Main()
        {
            Console.WriteLine("Enter N:");
            string stringInput = Console.ReadLine();
            int[] a = new int[Convert.ToInt16(stringInput)];

            Console.WriteLine("Enter profit values:");
            for (int i = 0; i < Convert.ToInt16(stringInput); i++)
            {
                string value = Console.ReadLine();
                a[i] = Convert.ToInt16(value);
            }

            int maxSum = maxSumSub(a);
            Console.WriteLine(string.Format("{0} {1} {2}", seqStart, seqEnd, maxSum));
            Console.ReadKey();
        }

        #endregion
    }

この部分を理解できない場合を除いて、複数の回答がある場合、プログラムは駐車場の数が最も少ないものを作成する必要があります。

4

2 に答える 2

0

これは古典的な最大サブセット和問題です。これは宿題なのでコードはありませんが、一般的な解決策は次のとおりです。それでも問題が解決しない場合は、タイトルを検索してオンラインでコードを見つけることができると確信しています。

  1. 最大サブセットの最初/最後のインデックス変数を作成します。これらは、回答の駐車スペースを保持します。あなたの例ではそれぞれ3と6です。
  2. 最大サブセットの合計の合計変数を作成します。これは、私たちの答えの合計を保持します。あなたの例では8。
  3. 「現在の」変数となる最初/最後/合計変数の別のセットを作成します。
  4. 駐車スペースの始まりから始めます。現在の最初と現在の最後の変数を先頭に配置し、合計を更新します。
  5. 次に、現在の最後の変数を移動して合計を更新することにより、各駐車スペースをループします。
  6. 現在の合計が max-so-far の合計よりも大きい場合、すべての現在の変数を max-so-far 変数に保存します。
  7. 任意の時点で現在の合計がマイナスになるかゼロになった場合、サブセットは最大値を取得するのに役立たないため、最初に現在を現在の最後の場所に移動し、現在の合計をゼロにリセットして再起動します。
  8. 最後に到達したら、max-so-far 変数を返します
于 2012-06-13T07:05:56.930 に答える
0

アルゴリズムをより効率的にする方法のヒントを次に示します。両端の合計がどのようになるかを見てください。たとえば、あなたが提供したものから、合計は左側から-5、-5、2、-4、0、3、-2、-2、0になり、右側からは2、2になります、-3、0、4、-2、5、5、0。

于 2012-06-13T07:08:27.863 に答える