问题描述
各位大大大神，我也是蛋疼的背包问题：假设有一个能装入总体积为T的背包和n件体积分别为w1，w2，。。。wn的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1+w2+。。。+wn=T，要求找出所有满足上述条件的解。例如，当T=10，各物品的体积分别为{1,8,4,3,2,5}时，可找出下列4组解：（1,4,3,2）（1,4,5）（8,2）（3,5,2）。基本要求1。设计一个背包问题的函数2。编写一个测试主函数。测试数据T=10，各物品的体积为{1,8,4,3,2,5}.
解决方案
解决方案二：
回帖加分（传说可以顶上去）
解决方案三：
staticvoidMain(string[]args){inttotal=10;int[]items=newint[]{1,8,4,3,2,5};intlength=items.Length;intnum=1;for(inti=0;i<length;i++){num*=2;}for(inti=0;i<num;i++){int[]resules=newint[length];int[]flags=ConvertInt(length,i);if(flags.Length!=items.Length){thrownewException();}for(intj=0;j<length;j++){resules[j]=items[j]*flags[j];}strings=string.Empty;if(Sum(resules)==total){for(intj=0;j<length;j++){if(resules[j]!=0){s+=resules[j]+",";}}}if(!string.IsNullOrEmpty(s)){Console.WriteLine("{{{0}}}",s.Trim(','));}}Console.ReadLine();}staticint[]ConvertInt(intnum,inti){int[]flags=newint[num];while(i!=0){flags[--num]=i%2;i=i/2;}returnflags;}staticintSum(int[]items){intsum=0;for(inti=0;i<items.Length;i++){sum+=items[i];}returnsum;}
解决方案四：
staticvoidMain(string[]args){inttotal=10;int[]items=newint[]{1,2,3,4,5,6,7,8,9};intnum=(int)Math.Pow((double)2,(double)items.Length);for(inti=0;i<num;i++){int[]results=newint[items.Length];int[]flags=ConvertInt(items.Length,i);for(intj=0;j<items.Length;j++){results[j]=items[j]*flags[j];}if(Sum(results)==total){Print(results);}}Console.ReadLine();}staticint[]ConvertInt(intnum,inti){int[]flags=newint[num];while(i!=0){flags[--num]=i%2;i=i/2;}returnflags;}staticintSum(int[]items){intsum=0;for(inti=0;i<items.Length;i++){sum+=items[i];}returnsum;}staticvoidPrint(int[]results){strings=string.Empty;for(intj=0;j<results.Length;j++){if(results[j]!=0){s+=results[j]+",";}}Console.WriteLine("{{{0}}}",s.Trim(','));}
解决方案五：
进来看看，顺便拿分。
解决方案六：
该回复于2011-06-20 13:34:52被版主删除
解决方案七：
有没有用C语言实现的？
解决方案八：
该回复于2012-03-09 08:33:51被版主删除
解决方案九：
课堂作业，不会的话正好找个女同学请教一下，顺便....
解决方案十：
使用递归算法staticvoidMain(){intbagCapacity=10;int[]stuff=newint[]{1,2,3,4,5,8};stringstuffs="";for(inti=0;i<stuff.Length;i++)stuffs+=stuff[i]+",";stringsolution="";bagSolution(bagCapacity,stuffs,solution);}staticvoidbagSolution(intCapacity,stringStuff,stringSolution){string[]Stuffs=Stuff.Split(',');for(inti=0;i<Stuffs.Length-1;i++){if(Capacity-int.Parse(Stuffs[i])==0){Solution+=Stuffs[i];Stuff="";for(intj=0;j<Stuffs.Length-1;j++)if(j!=i)Stuff+=Stuffs[j]+",";Console.Write(Solution+"n");}elseif(Capacity-int.Parse(Stuffs[i])>0){Capacity-=int.Parse(Stuffs[i]);stringtemStr=Solution;Solution+=Stuffs[i]+",";Stuff="";for(intj=0;j<Stuffs.Length-1;j++)if(j!=i)Stuff+=Stuffs[j]+",";bagSolution(Capacity,Stuff,Solution);Capacity+=int.Parse(Stuffs[i]);Solution=temStr;}}}