在 中讲述了一个开发的场景，首先有一个总共的土地拥有量：total亩，现在有n种可以选择的商品，每一种商品都有每亩的用量：amount/亩，每一种商品都有多个包装规格，每个包装规格有自己的包装量和售价。

　　需求就是计算出，在给定土地上面种植那种商品需要的花费最少，也就是可以用最少的钱来买更多的东西种地，满足我种地的{zd0}需求量。

　　其实我们还假设了一个前提，就是包装大的单价低，好比100克每包的可能买100元，200克每包的就应该卖180元，肯定会小于两个100克每包的价格，这个也是市场调研的结果，也比较符合市场常规。

　　代码中用到了二分搜索法的思路，其实我需要的是一个定位，定位我需要购买的最合算的包装规格，也就是在满足需要的情况下，尽可能购买大包装。

　　例如：现在有两个商品，土豆和白菜，土豆有三个规格，100克每包的100元，200克每包的180元，300克每包的240元；白菜有四个规格，100克每包的70元，200克每包的130元，300克每包的200元，400克每包的300元。种白菜每亩要100斤，中土豆每亩尧200斤。我总共有1029亩地，计算一下，是种土豆花费少？还是种白菜花费少？

　　有两个点要注意：1）找位置，找到我需要购买的最合算的包装规格的位置，使用了二分搜索2）计算用量和预算。

　　计算一种商品最少花费的伪代码如下：

　　输入：一个商品的信息，包括包装规格

　　输出:需要购买的包装规格几个数，总共的花费

　　计算过程：

　　{

　　　　while（总量>最小包装规格的量）

　　　　{

　　　　　　1）找位置，定位包装规格

　　　　　　2）计算需要购买多少个{dy}步找到的包装规格

　　　　　　3）需要购买的个数=总量和包装规格的包装量取整

　　　　　　4）总量=总量-需要购买的个数*包装规格的包装量

　　　　　　5）这种商品的预算+=需要购买的个数*包装规格的单价

　　　　}

　　　　if（总量<=最小包装规格的量）

　　　　{

　　　　　　说明零头就只能买个最小包装了，因为购买不支持散买。

　　　　}

　　}

　　示例代码下载：

　　代码如下：

代码

/*
 * Created by SharpDevelop.
 * User: haier
 * Date: 2010-3-23
 * Time: 22:19
 * 
 * To change this template use Tools | Options | Coding | Edit Standard Headers.
 */
using System;
using System.Collections.Generic;

namespace BeautyCode.ConApp
{
    /// <summary>
    /// 种植方案
    /// </summary>
    public class PlantArea
    {
        /// <summary>
        /// 种植面积,单位是亩
        /// </summary>
        public static decimal PlantAreaAmount=175.25m;
    }
    /// <summary>
    /// 商品类型
    /// </summary>
    public enum ProductType
    {
        /// <summary>
        /// 种子
        /// </summary>
        Seed,
        /// <summary>
        /// 肥料
        /// </summary>
        Fertilizer,
        /// <summary>
        /// 农药
        /// </summary>
        Pesticide
    }
    
    public enum FertType
    {
        /// <summary>
        /// 底肥
        /// </summary>
        DiF,
        /// <summary>
        /// 种肥
        /// </summary>
        ZhongF,
        /// <summary>
        /// 追肥
        /// </summary>
        ZhuiF
    }
    public class Unit
    {
        public Guid ID{set;get;}
        
        public string CnName{set;get;}
    }
    public class PkgPrice
    {
        public Guid PkgID{set;get;}
        /// <summary>
        /// 包装量
        /// </summary>
        public decimal PkgAmount{set;get;}
        /// <summary>
        /// 包装单位
        /// </summary>
        public Unit PkgUnit{set;get;}
        /// <summary>
        /// 包装价格
        /// </summary>
        public decimal Price{set;get;}
        /// <summary>
        /// 选中的包装个数
        /// </summary>
        public int Quantities{set;get;}
    }
    
    public class Product
    {
        public virtual Guid ID{set;get;}
        public virtual string Name{set;get;}
        public virtual ProductType ProType{set;get;}
        /// <summary>
        /// 每亩用量
        /// </summary>
        public virtual decimal Amount{set;get;}
        /// <summary>
        /// 每亩用量单位
        /// </summary>
        public virtual Unit ProductUnit{set;get;}
        /// <summary>
        /// 总用量
        /// </summary>
        public virtual decimal TotalAmount{set;get;}
        public Product (ProductType type)
        {
            this.ProType=type;
        }
        /// <summary>
        /// 预算
        /// </summary>
        public decimal Budget{set;get;}
        /// <summary>
        /// 全部包装类型
        /// </summary>
        public List<PkgPrice > AllPkgPrice{set;get;}
        /// <summary>
        /// 选中的包装类型
        /// </summary>
        public List<PkgPrice > SelectPkgPrice{set;get;}
    }
    public class Seed:Product 
    {
        public Seed ():base(ProductType.Seed ){}
        
        public List<Pesticide > Pesticides{set;get;}
        public List<DiF > DiFs{set;get;}
        public List<ZhongF >ZhongFs{set;get;}
        public List<ZhuiF >ZhuiFs{set;get;}
    }
    public class Fertilizer:Product 
    {public FertType FType{set;get;}
        public Fertilizer (FertType type):base (ProductType.Fertilizer){
        this.FType=type ;
        }
    }
    public class DiF:Fertilizer 
    {
        public DiF ():base (FertType.DiF ){}
    }
    public class ZhongF:Fertilizer 
    {
        public ZhongF ():base (FertType .ZhongF ){}
    }
    public class ZhuiF:Fertilizer 
    {
        public ZhuiF ():base (FertType.ZhuiF ){}
    }
    public class Pesticide:Product 
    {
        public Pesticide ():base(ProductType.Pesticide ){}
    }
    /// <summary>
    /// Description of BeiBao.
    /// </summary>
    public class BeiBao
    {
        public List<Seed  >Seeds=null;
        public Seed  Seed=null;
        public List<Pesticide >Pesticides=null;
        public Pesticide Pesticide=null;
        public List<DiF >DiFs=null;
        public DiF DiF=null;
        public List<ZhongF >ZhongFs=null;
        public ZhongF ZhongF=null;
        public List<ZhuiF >ZhuiFs=null;
        public ZhuiF ZhuiF=null;
        public List<PkgPrice > PkgPrices=null;
        public BeiBao()
        {
            Seeds =new List<Seed  >();
            Seed =new Seed(){ ID=Guid.NewGuid (),
                Name="土豆", Amount =120, Budget=0,
                TotalAmount =120*PlantArea.PlantAreaAmount };
            PkgPrices =new List<PkgPrice>(){
                new PkgPrice (){ PkgID=Guid.NewGuid (),PkgAmount =100, Price=23},
                new PkgPrice (){ PkgID=Guid.NewGuid (),PkgAmount =210, Price=58},
                new PkgPrice (){ PkgID=Guid.NewGuid (),PkgAmount =130, Price=39}};
            Seed .AllPkgPrice =PkgPrices ;
            Seed.AllPkgPrice.Sort(new Comparison<PkgPrice >(comparePkgAmountAsc));
            Seeds.Add(Seed );
            Seed =new Seed(){ ID=Guid.NewGuid (),
                Name="白菜", Amount =150, Budget=0, TotalAmount =150*PlantArea.PlantAreaAmount };
            PkgPrices =new List<PkgPrice>(){
                new PkgPrice (){ PkgID=Guid.NewGuid (),PkgAmount =80, Price=20},
                new PkgPrice (){ PkgID=Guid.NewGuid (),PkgAmount =180, Price=48},
                new PkgPrice (){ PkgID=Guid.NewGuid (),PkgAmount =110, Price=34}};
            Seed .AllPkgPrice =PkgPrices ;
                Seed.AllPkgPrice.Sort(new Comparison<PkgPrice >(comparePkgAmountAsc));
            Seeds.Add(Seed );
            Seed =new Seed(){ ID=Guid.NewGuid (),
                Name="萝卜", Amount =100, Budget=0, TotalAmount =100*PlantArea.PlantAreaAmount };
            PkgPrices =new List<PkgPrice>(){
                new PkgPrice (){ PkgID=Guid.NewGuid (),PkgAmount =110, Price=35},
                new PkgPrice (){ PkgID=Guid.NewGuid (),PkgAmount =250, Price=79},
                new PkgPrice (){ PkgID=Guid.NewGuid (),PkgAmount =170, Price=49}};
            Seed .AllPkgPrice =PkgPrices ;
                Seed.AllPkgPrice.Sort(new Comparison<PkgPrice >(comparePkgAmountAsc));
            Seeds.Add(Seed );
            Seed =new Seed(){ ID=Guid.NewGuid (),
                Name="大豆", Amount =20, Budget=0, TotalAmount =20*PlantArea.PlantAreaAmount };
            PkgPrices =new List<PkgPrice>(){
                new PkgPrice (){ PkgID=Guid.NewGuid (),PkgAmount =110, Price=35},
                new PkgPrice (){ PkgID=Guid.NewGuid (),PkgAmount =250, Price=79},
                new PkgPrice (){ PkgID=Guid.NewGuid (),PkgAmount =170, Price=49}};
            Seed .AllPkgPrice =PkgPrices ;
                Seed.AllPkgPrice.Sort(new Comparison<PkgPrice >(comparePkgAmountAsc));
            Seeds.Add(Seed );
        }
        
        public Product ComputeOptimized()
        {
            
            foreach (Product p in this.Seeds  )
            {
                GetTotalBudget ( p);
            }
            Seeds.Sort (new Comparison<Seed  >(compareProductBudgetAsc ));
            return Seeds[0];
        }
        private void  GetTotalBudget(Product p)
        {
            p.SelectPkgPrice=new List<PkgPrice>();
            int index=-1;
            int quantities=0;
            decimal totalamount=p.TotalAmount;
            while (totalamount >p.AllPkgPrice [0].PkgAmount )
            {
                index =binaryLocalize (p.AllPkgPrice,totalamount,p.AllPkgPrice.Count );
                if(index !=-1)
                {
                    quantities =(int)(totalamount /p.AllPkgPrice [index ].PkgAmount );
                    //quantities =(int)(totalamount %p.AllPkgPrice [index ].PkgAmount );
                    p.SelectPkgPrice.Add(new PkgPrice (){
                                             PkgID=p.AllPkgPrice[index].PkgID ,
                                             PkgAmount=p.AllPkgPrice[index].PkgAmount,
                                             Price=p.AllPkgPrice[index].Price ,
                                             Quantities=quantities 
                                         });
                    p.Budget +=quantities *p.AllPkgPrice[index].Price ;
                }
                totalamount -=quantities *p.AllPkgPrice[index].PkgAmount;
            }
            if(totalamount !=0)
            {
                quantities =1;
                index =0;
                p.SelectPkgPrice.Add(new PkgPrice (){
                                             PkgID=p.AllPkgPrice[index].PkgID ,
                                             PkgAmount=p.AllPkgPrice[index].PkgAmount,
                                             Price=p.AllPkgPrice[index].Price ,
                                             Quantities=quantities 
                                         });
                    p.Budget +=quantities *p.AllPkgPrice[index].Price ;
            }
            
        }
        /// <summary>
        /// 二分法搜索元素
        /// </summary>
        /// <param name="a"></param>
        /// <param name="x"></param>
        /// <param name="n"></param>
        /// <returns></returns>
        private int binarySearch(List<int >a,int x,int n)
        {
            int left=0;
            int right=n-1;
            while (left <=right)
            {
                int middle=(left +right )/2;
                if(x==a[middle])return middle;
                if(x>a[middle ])left =middle +1;
                else right =middle -1;
            }
            //没有找到
            return -1;
        }
        /// <summary>
        /// 二分法定位规格
        /// </summary>
        /// <param name="pkgPrices"></param>
        /// <param name="totalAmount"></param>
        /// <param name="n"></param>
        /// <returns></returns>
        private int binaryLocalize(List<PkgPrice > pkgPrices,decimal  totalAmount,int n)
        {
            if(totalAmount >=pkgPrices [n-1].PkgAmount )
                return n-1;
            
            int left=0;
            int right=n-1;
            while (left <=right )
            {
                int middle=(left+right )/2;
                if(totalAmount >=pkgPrices [middle ].PkgAmount &&totalAmount <pkgPrices [middle +1].PkgAmount )
                {
                    return middle ;
                }
                 if(totalAmount ==pkgPrices [middle +1].PkgAmount )
                {
                    return middle +1;
                }
                 if(totalAmount >pkgPrices [middle +1].PkgAmount )
                     left =middle +1;
                 else
                     right =middle -1;
            }
            return -1;
        }
        private int compareProductBudgetAsc(Product pro1,Product pro2)
        {
            if(pro1.Budget>pro2 .Budget )
                return 1;
            if(pro1.Budget<pro2 .Budget )
                return -1;
            else 
                return 0;
        }
        
        private int comparePkgAmountAsc(PkgPrice pkg1,PkgPrice pkg2)
        {
            if(pkg1.PkgAmount >pkg2.PkgAmount )
                return 1;
            if(pkg1.PkgAmount <pkg2 .PkgAmount )
                return -1;
            else 
                return 0;
        }
    }
}

调用代码

代码

/*
 * Created by SharpDevelop.
 * User: haier
 * Date: 2010-3-21
 * Time: 1:02
 * 
 * To change this template use Tools | Options | Coding | Edit Standard Headers.
 */
using System;

namespace BeautyCode.ConApp
{
    class Program
    {
        public static void Main(string[] args)
        {
            Console.WriteLine("Hello World!");
            
            // TODO: Implement Functionality Here
            BeiBao bag=new BeiBao();
            Product product=    bag.ComputeOptimized ();
            
            Console.Write("Press any key to continue . . . ");
            Console.ReadKey(true);
        }
    }
}