递归 背包问题.doc

《递归 背包问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、packagecom.neil.algorithms;/***递归求01背包问题**@authorneil*@date下午12:01:27*@filenameBagProblem.java*/publicclassBagProblem{publicstaticvoidmain(String[]args){int[]array=newint[]{1,2,3,4,2,4,11,23,43,12,6};knap(12,array.length-1,array);}publicstaticbooleanknap(intm,intn,int[]array){//如果放入的质

2、量等于包剩余的容量if(m==array[n]){System.out.print(array[n]+"");returntrue;//如果放入的质量小于包剩余的容量}elseif(m>array[n]){//如果还有剩余物品//如果放入这个之后,knap(m-array[n],n-1,array)有解,那么就放入这个if(n>0){if(knap(m-array[n],n-1,array)){System.out.print(array[n]+"");returntrue;//如果放入这个之后,knap(m-array[n],n-1,array)无解,那么就考虑

3、knap(m,n-1,array)}else{returnknap(m,n-1,array);}//如果没有剩余物品了。}else{returnfalse;}//如果当前放入的质量大于背包剩余容量}else{//如果还有剩余物品可以放入if(n>0){returnknap(m,n-1,array);//如果没有剩余物品可以放入}elsereturnfalse;}}}