问题描述
例：1、数据库有N条用户需求，张二10000元，张三8000元，张四5000元，李三8000元.....需求的人无限...2、数据库提供的供应者也是N条，王二提供5000元，王三提供8000元，王四提供7000元，王五提供1000元，王六提供10000元....无限匹配1个或多个供应者。如有单个供应者正好提供10000元，就匹配单个供应者。如没有就匹配：9000+1000，或8000+2000，或7000+2000+1000。。。。匹配成功的放入相应数据表。求最优算法。谢谢！
解决方案
本帖最后由 aite520 于 2015-11-02 15:44:45 编辑
解决方案二：
如下算法的复杂度为O(N*Log(N))。代码没有注释，楼主/有兴趣的朋友，或请加注释。publicstaticList<int>CombineTo(inttotal,List<int>items){if(items.Any(i=>i<=0))thrownewInvalidOperationException("onlypositivenumbersallowed.");items.Sort();//O(n*Log(n))List<int>result=newList<int>();if(CombineTo(total,items,0,items.Count,result)!=total){result.Clear();}returnresult;}privatestaticintCombineTo(inttotal,List<int>sortedItems,intoffset,intlength,List<int>result){inti=sortedItems.BinarySearch(offset,length,total,Comparer<int>.Default);//O(Log(n))if(i>=0){result.Add(sortedItems[i]);returntotal;}i=(~i)-1;for(intj=i;j>0;j--){intsubTotal=total-sortedItems[j];intachieved=CombineTo(subTotal,sortedItems,0,j,result);if(achieved==subTotal){result.Add(sortedItems[i]);returntotal;}if(achieved<subTotal)break;//凑不齐的情况下，CombineTo最多调用n次。}return0;}publicstaticvoidTest(){List<int>items=newList<int>(){2,8,1,5};varr0=CombineTo(0,items);//{}varr1=CombineTo(1,items);//{1}varr2=CombineTo(2,items);//{2}varr3=CombineTo(3,items);//{1,2}varr4=CombineTo(4,items);//{}varr5=CombineTo(5,items);//{5}varr6=CombineTo(6,items);//{1,5}varr7=CombineTo(7,items);//{2,5}varr8=CombineTo(8,items);//{8}varr9=CombineTo(9,items);//{1,8}varr10=CombineTo(10,items);//{2,8}varr11=CombineTo(11,items);//{1,2,8}varr12=CombineTo(12,items);//{}varr13=CombineTo(13,items);//{5,8}varr14=CombineTo(14,items);//{1,5,8}varr15=CombineTo(15,items);//{2,5,8}varr16=CombineTo(16,items);//{1,2,5,8}varr17=CombineTo(17,items);//{}}
解决方案三：
补充一下问题。还有个情况就是供应者可以拆分自己提供的金额和需求者匹配比如：1、需求者：张三1000元，张四1000元2、供应者：王三提供2000元系统可以把王三拆分为两个1000，分别和张三、张四匹配
解决方案四：
你这个是哪里的试题么？
解决方案五：
都可以拆了，还有什么是不可以的？