网络资源的拷贝粘贴 备份参考之用


24 January 2011

0/1 KnapSack problem in C#


The following program find a best solution in 0/1 KnapSack problem, but it does not pick all the best solutions.

        public static int CalculateBagProblem(int BagVolumn, List<int> items, out List<int> chosenItems)

        {

            chosenItems = new List<int>();

            if (items.Count == 0)

            {  

                return 0;

            }

            else if (items.Count == 1)

            {

                if (items[0] <= BagVolumn)

                {

                    chosenItems.Add(items[0]);

                    return items[0];

                }

                else

                {

                    return 0;

                }

            }

            else

            {

                // without the first item

                List<int> remainItems = items.GetRange(1, items.Count - 1);

                List<int> chosenItemsInRemainItems = new List<int>();

                int withoutFirstItemResult = CalculateBagProblem(BagVolumn, remainItems, out chosenItemsInRemainItems);

                

                // with all the items

                int withFirstItemResult = 0;

                List<int> chosenItemsInItems = new List<int>();

                if (BagVolumn >= items[0])

                {

                    withFirstItemResult = CalculateBagProblem(BagVolumn - items[0], remainItems, out chosenItemsInItems) + items[0];

                    chosenItemsInItems.Add(items[0]);

                }

 

                // select max from the two results               

                if (withoutFirstItemResult >= withFirstItemResult)

                {

                    chosenItems = chosenItemsInRemainItems;

                    return withoutFirstItemResult;

                }

                else

                {

                    chosenItems = chosenItemsInItems;

                    return withFirstItemResult;

                }

            }

        }

 



No comments:

Google