关于背包问题的进一步优化

上一篇写的方法因为包含递归，当组合变多时速度降得很快，而且出现重复，以下改成循环方法，并且减少了重复:

先定义商品类：

 /// <summary>
    /// 商品类
    /// </summary>
    public class Good
    {
        /// <summary>
        /// 此处假定Id是唯一的
        /// </summary>
        public string Id { get; set; }
        public string TypeName { get; set; }
        public int Price { get; set; }
    }

定义商品组合类，其中封装了一个商品list以及对它进行添加和删除个体的方法：

 public class Goods
    {
        public List<Good> GoodList { get; set; }
        public int TotalPrice
        {
            get
            {
                int result = 0;
                foreach (Good g in GoodList)
                    result += g.Price;
                return result;
            }
        }
        public Goods()
        {
            GoodList = new List<Good>();
        }
        public Goods(Good g)
            : this()
        {
            GoodList.Add(g);
        }
        public void AddGood(Good g)
        {
            GoodList.Add(g);
        }
        public void RemoveLastGood()
        {
            if (GoodList.Count > 0)
                GoodList.RemoveAt(GoodList.Count - 1);
        }
    }

定义测试类，用于输入一个总额，进行自动组合，输出符合要求的所有组合：

 public class Test
    {
        private List<Good> goodList;
        private int _totalprice;
        public Test(int totalprice)
        {
            //以下是自测试随机生成商品和价格列表，实际应用中可以用select语句获取所有单价小于totalprice的商品列表            
            goodList = new List<Good>();            
            for (int i = 0; i < 5; i++)
            {
                goodList.Add(new Good()
                {
                    Id = string.Format("第{0}个商品", (i + 1).ToString()),
                    TypeName=(i+1).ToString(),
                    Price = (i + 1) * 10
                });
            }
            goodList.Add(new Good()
            {
                Id = string.Format("第{0}个商品",(goodList.Count+1).ToString()),
                TypeName = (goodList.Count + 1).ToString(),
                Price = 5
            });
            _totalprice = totalprice;
            //下面是添加可能重复的项，目的是提高速度
            int count = goodList.Count;            
            int percount = 0;
            Good g;
            for (int i = 0; i < count; i++)
            {
                g=goodList[i];
                percount = totalprice / g.Price;
                for (int j = 1; j < percount; j++)
                {
                    goodList.Add(new Good()
                    {
                        Id = string.Format("第{0}个商品的{1}个重复", (i + 1).ToString(),(j+1).ToString()),
                        TypeName=(i + 1).ToString(),
                        Price = g.Price*(j+1)
                    });
                }
            }
        }
        public List<List<Good>> GetAllSelection()
        {
            List<List<Good>> result = new List<List<Good>>();
            List<Good> goodsort = goodList.OrderByDescending(e => e.Price).ToList();
            Good good;
            for (int i = 0; i < goodsort.Count;i++ )
            {
                good = goodsort[i];
                if (good.Price == _totalprice)
                    result.Add(new List<Good>() { good });
                else
                {
                    Goods goods = new Goods(good);
                    for (int j = goodsort.Count - 1; j > i&&goods.TotalPrice<_totalprice; j--)
                    {
                        string typename = goodsort[j].TypeName;
                        if (goods.GoodList.Find(e => e.TypeName==typename) != null)
                            continue;
                        goods.AddGood(goodsort[j]);
                        if (goods.TotalPrice == _totalprice)
                        {
                            result.Add(goods.GoodList.ToList());
                            goods.RemoveLastGood();
                        }
                        else if (goods.TotalPrice > _totalprice&&goods.GoodList.Count>2)
                        {
                            goods.RemoveLastGood();
                            goods.RemoveLastGood();
                            j++;
                            continue;
                        }
                    }
                }                
            }
            return result;
        }
    }

最后在主程序进行测试：

  /// <summary>
    /// MainWindow.xaml 的交互逻辑
    /// </summary>
    public partial class MainWindow : Window
    {
        public MainWindow()
        {
            InitializeComponent();


            //Test test = new Test(100);
            Extend.Test test = new Extend.Test(50);
            List<List<Extend.Good>> resulttest = test.GetAllSelection();
            StringBuilder sb=new StringBuilder();
            for (int i = 0; i < resulttest.Count;i++ )
            {
                sb.Append("\r\n");
                for (int j = 0; j < resulttest[i].Count;j++ )
                {
                    sb.Append(resulttest[i][j].Id.ToString() + ",");
                }
            }
            Console.WriteLine(sb.ToString());
        }
    }

输出：

第5个商品,
第1个商品的5个重复,
第6个商品的10个重复,
第4个商品,第1个商品,
第2个商品的2个重复,第1个商品,
第6个商品的8个重复,第1个商品,
第3个商品,第2个商品,
第1个商品的3个重复,第2个商品,
第6个商品的6个重复,第2个商品,