背包算法

今天在社区帮人解答某个算法问题，其中有位朋友提出了背包问题的算法，特把他的方法贴在这里收藏一下：

1. namespaceProgram
2. {
3. publicclassPackage
4. {
5. publicdouble[]goods=newdouble[]{1,1.1,2,3,4};
7. ///<summary>
8. ///用递归算出
9. ///</summary>
10. ///<paramname="puts">目前放入背包的数</param>
11. ///<paramname="unPuts">可放入背包的数</param>
12. ///<paramname="sum">背包还剩的容量</param>
13. publicvoidShowComposes(List<double>puts,double[]unPuts,doublesum)
14. {
15. //输出当前放入背包符合条件的所有数
16. boolexist=false;
17. foreach(doubledinputs)
18. {
19. System.Console.Write(d+"");
20. exist=true;
21. }
22. if(exist)
23. System.Console.WriteLine();
25. //在可放入背包的数字中，选择可放的数并放进背包
26. foreach(doubledinunPuts)
27. {
28. if(d<sum)
29. {
30. List<double>newPuts=puts.ToList<double>();
31. newPuts.Add(d);
32. ShowComposes(newPuts,goods,sum-d);
33. }
34. }
35. }
37. staticvoidMain(string[]args)
38. {
39. Packagep=newPackage();
40. p.ShowComposes(newList<double>(),p.goods,6);
41. }
42. }
43. }

原帖地址:http://topic.csdn.net/u/20080827/13/3fbba373-8882-4d22-a0f2-2188b0ba2ef6.html