■ 분할 문제 해결을 위한 분기와 초기 휴리스틱 바인딩 사용하기

------------------------------------------------------------------------------------------------------------------------


TestProject.zip


MainForm.cs

 

 

using System;

using System.Linq;

using System.Text;

using System.Windows.Forms;

 

namespace TestProject

{

    /// <summary>

    /// 메인 폼

    /// </summary>

    public partial class MainForm : Form

    {

        //////////////////////////////////////////////////////////////////////////////////////////////////// Constructor

        ////////////////////////////////////////////////////////////////////////////////////////// Public

 

        #region 생성자 - MainForm()

 

        /// <summary>

        /// 생성자

        /// </summary>

        public MainForm()

        {

            InitializeComponent();

 

            #region 이벤트를 설정한다.

 

            this.partitionButton.Click += partitionButton_Click;

 

            #endregion

        }

 

        #endregion

 

        //////////////////////////////////////////////////////////////////////////////////////////////////// Method

        ////////////////////////////////////////////////////////////////////////////////////////// Private

        //////////////////////////////////////////////////////////////////////////////// Event

 

        #region 분할 버튼 클릭시 처리하기 - partitionButton_Click(sender, e)

 

        /// <summary>

        /// 분할 버튼 클릭시 처리하기

        /// </summary>

        /// <param name="sender">이벤트 발생자</param>

        /// <param name="e">이벤트 인자</param>

        private void partitionButton_Click(object sender, EventArgs e)

        {

            Cursor = Cursors.WaitCursor;

 

            this.resultListTextBox1.Clear();

            this.resultListTextBox2.Clear();

 

            this.totalResultTextBox1.Clear();

            this.totalResultTextBox2.Clear();

 

            Application.DoEvents();

 

            DateTime startTime = DateTime.Now;

 

            string[] valueStringArray = this.valueListTextBox.Lines;

 

            int[] valueArray = new int[valueStringArray.Length];

 

            for(int i = 0; i < valueStringArray.Length; i++)

            {

                valueArray[i] = int.Parse(valueStringArray[i]);

            }

 

            bool[] bestAssignmentArray = GetBestAssignmentArray(valueArray);

 

            StringBuilder resultStringBuilder1 = new StringBuilder();

            StringBuilder resultStringBuilder2 = new StringBuilder();

 

            int totalResult1 = 0;

            int totalResult2 = 0;

 

            for(int i = 0; i < bestAssignmentArray.Length; i++)

            {

                if (bestAssignmentArray[i])

                {

                    resultStringBuilder1.AppendLine(valueArray[i].ToString());

 

                    totalResult1 += valueArray[i];

                }

                else

                {

                    resultStringBuilder2.AppendLine(valueArray[i].ToString());

 

                    totalResult2 += valueArray[i];

                }

            }

 

            this.resultListTextBox1.Text = resultStringBuilder1.ToString();

            this.resultListTextBox2.Text = resultStringBuilder2.ToString();

 

            this.totalResultTextBox1.Text = totalResult1.ToString();

            this.totalResultTextBox2.Text = totalResult2.ToString();

 

            DateTime stopTime = DateTime.Now;

 

            Cursor = Cursors.Default;

 

            TimeSpan elapsed = stopTime - startTime;

 

            this.elapsedLabel.Text = elapsed.TotalSeconds.ToString("0.00") + " 초";

        }

 

        #endregion

 

        //////////////////////////////////////////////////////////////////////////////// Function

 

        #region 탐욕적 값 배열 분할하기 - PartitionValueArrayGreedy(valueArray, bestAssignmentArray, bestError)

 

        /// <summary>

        /// 탐욕적 값 배열 분할하기

        /// </summary>

        /// <param name="valueArray">값 배열</param>

        /// <param name="bestAssignmentArray">최적 할당 배열</param>

        /// <param name="bestError">최적 오차</param>

        private void PartitionValueArrayGreedy(int[] valueArray, bool[] bestAssignmentArray, ref int bestError)

        {

            int total1 = 0;

            int total2 = 0;

 

            for(int i = 0; i < bestAssignmentArray.Length; i++)

            {

                if(total1 <= total2)

                {

                    bestAssignmentArray[i] = true;

 

                    total1 += valueArray[i];

                }

                else

                {

                    total2 += valueArray[i];

                }

            }

 

            bestError = Math.Abs(total1 - total2);

        }

 

        #endregion

        #region 인덱스에서 값 배열 분할하기 - PartitionValueArrayFromIndex(valueArray, startIndex, totalValue, unassignedValue,

            testAssignmentArray, testValue, bestAssignmentArray, bestError)

 

        /// <summary>

        /// 인덱스에서 값 배열 분할기

        /// </summary>

        /// <param name="valueArray">값 배열</param>

        /// <param name="startIndex">시작 인덱스</param>

        /// <param name="totalValue">전체 값</param>

        /// <param name="unassignedValue">미할당 값</param>

        /// <param name="testAssignmentArray">테스트 할당 배열</param>

        /// <param name="testValue">테스트 값</param>

        /// <param name="bestAssignmentArray">최적 할당 배열</param>

        /// <param name="bestError">최적 오차</param>

        private void PartitionValueArrayFromIndex(int[] valueArray, int startIndex, int totalValue, int unassignedValue,

            bool[] testAssignmentArray, int testValue, ref bool[] bestAssignmentArray, ref int bestError)

        {

            if(startIndex >= valueArray.Length)

            {

                int testError = Math.Abs(2 * testValue - totalValue);

 

                if(testError < bestError)

                {

                    bestError = testError;

 

                    bestAssignmentArray = (bool[])testAssignmentArray.Clone();

                }

            }

            else

            {

                int testError = Math.Abs(2 * testValue - totalValue);

 

                if(testError - unassignedValue < bestError)

                {

                    unassignedValue -= valueArray[startIndex];

 

                    testAssignmentArray[startIndex] = true;

 

                    PartitionValueArrayFromIndex

                    (

                        valueArray,

                        startIndex + 1,

                        totalValue,

                        unassignedValue,

                        testAssignmentArray,

                        testValue + valueArray[startIndex],

                        ref bestAssignmentArray,

                        ref bestError

                    );

 

                    testAssignmentArray[startIndex] = false;

 

                    PartitionValueArrayFromIndex

                    (

                        valueArray,

                        startIndex + 1,

                        totalValue,

                        unassignedValue,

                        testAssignmentArray,

                        testValue,

                        ref bestAssignmentArray,

                        ref bestError

                    );

                }

            }

        }

 

        #endregion

        #region 최적 할당 배열 구하기 - GetBestAssignmentArray(valueArray)

 

        /// <summary>

        /// 최적 할당 배열 구하기

        /// </summary>

        /// <param name="valueArray">값 배열</param>

        /// <returns>최적 할당 배열</returns>

        private bool[] GetBestAssignmentArray(int[] valueArray)

        {

            bool[] bestAssignmentArray = new bool[valueArray.Length];

            bool[] testAssignmentArray = new bool[valueArray.Length];

 

            int totalValue = valueArray.Sum();

            int bestError  = totalValue;

 

            PartitionValueArrayGreedy(valueArray, bestAssignmentArray, ref bestError);

    

            PartitionValueArrayFromIndex

            (

                valueArray,

                0,

                totalValue,

                totalValue,

                testAssignmentArray,

                0,

                ref bestAssignmentArray,

                ref bestError

            );

 

            return bestAssignmentArray;

        }

 

        #endregion

    }

}

 

------------------------------------------------------------------------------------------------------------------------

Posted by 사용자 icodebroker
TAG

댓글을 달아 주세요