黑马程序员技术交流社区

标题: 经典算法题-背包问题的实现,递归的思想 [打印本页]

作者: ygxheima 时间: 2016-5-17 22:41
标题: 经典算法题-背包问题的实现,递归的思想
/*
//背包问题:想要背包精确的承重某个重量,在给定的n个重量选项中选出合适的组合,不需要选出所有的组合,只要有就停止工作.
如背包能准确承重20kg,在 {11,8,7,6,5}中选,我们可以和容易用肉眼看出8,7,5的组合就可以满足条件.但用计算机处理这个
却不是那么简单.我的思路如下:
-------------------------------------------------------------------------------------------------------------------------------------
解题思路:
1.创建一背包问题的类,该类中有一个能存储integer的列表用来存储符合所有元素的和满足背包承重的元素;
2.同时还有一个匹配目标重量的函数,该函数的返回值是Boolean型的,在该函数中,通过递归,可以向列表中添加满足条件的组合
如果满足了条件就停止并输出true;
3,最后提供一个对外的获得结果的方法,该方法有三个参数:
   @ param items 存储的可供选择的重量选项的数组
   @ param low 在items数组中开始找匹配结果的下标
   @ param target 需要匹配的重量和
--------------------------------------------------------------------------------------------------------------------------------------
/*
算法如下
1. 在选择的任何时刻,如果所选的数据项等于你所需要的总和重量,你的工作就可以停止了,此时你的函数输出true并停止
2 从第一个数据项开始选择,接下来选择的数据项的总和要等于总的重量减去第一个数据项的值,此时我们得到了一个新的目标总量
3 在选择的任何时刻,如果出现所选的值比要求的重量大,就可以直接跳过寻找下一个数据项
4 如果第一个数据项把所有方案遍历了一遍没有匹配的话就转到下一个数据项
5 如果所有方案试过以后没有结果就输出false

*/

public class MatchBag02 {
public static void main(String[] args) {
BagQuestion bq = new BagQuestion();
int [] items = {11,8,7,6,5};
int target = 20;
bq.getResult(items,0,target);

}
}

class BagQuestion {
private ArrayList<Integer> arr = new ArrayList<Integer>();

public void  getResult(int [] items,int low, int target) {
if (matchBag(items,low,target) == false) {
System.out.println("没有合适的组合");
}else {
System.out.println("答案为:");
for (int i=0;i <arr.size() ;i ++ ) {
System.out.print( arr.get(i) + ",");
}
}

}

public boolean matchBag(int[] items, int low ,int target) {
//用递归的方法是需要终止递归的条件的
if(items[low] == target && low < items.length)
{//遇到相等就可以停止工作,输出true;
arr.add(items[low]);
return true;
}else if(low >= items.length-1) {//如果到了数组的末尾还没有匹配到就输出false;
return false;
}else if(items[low] > target) {//如果该数比目标值大就转到下一个元素
return matchBag(items,low+1,target);
}else {
for(int i = low +1;i < items.length; i ++) {//从他的下一个元素开始遍历匹配,如果有,则添加这个元素并输出true;
if(matchBag(items,i,target - items[low])) {
arr.add(items[low]);
return true;
}
}
return matchBag(items , low + 1 , target);//如果遍历完了这个数组依旧没有合适的匹配组合,则舍弃这个数据元素转到下一个元素
}
}

作者: 可以假装看不见 时间: 2016-5-17 22:50
学习了!!!

作者: orchild 时间: 2016-5-17 22:58
感谢分享！！！

作者: ajj1314 时间: 2016-5-17 23:11
已收藏，感觉有帮助。楼主大爱，嘎嘎！！！

作者: w19941102 时间: 2016-5-17 23:59
已收藏，感觉有帮助。

作者: ygxheima 时间: 2016-5-18 22:30
后续会继续写类似的算法题,对大家有帮助就行,谢谢大家了

作者: lf19920227 时间: 2016-5-18 22:33
不错不错

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2