首页 > 代码库 > 利用回溯法求解背包问题
利用回溯法求解背包问题
最近看完了利用回溯法求八皇后问题,最后成功求解到92种解法,然后在看利用贪心求解背包问题,突然想到其实也可以利用回溯法求解背包问题,本质上回溯法是一个穷举的方式在求.
回溯法求解出的结果肯定是正确的,这也可以验证自己所写的贪心算法的正确性.
问题描诉:
设定Wmax为最大重量,W[](0~n-1)为编号0~n-1的货物重量,V[](0~n-1)为其价值,x[]为其中解,
在wn=ΣXi*Wi<Wmax的条件下,求Vmax=ΣXi*Vi.
代码如下:
//全局变量最大价值int maxvalue=http://www.mamicode.com/0;
//当前最优解int an_x[10];//w为重量数组
//va为价值数组
//wmax为最大的重量
//n为货物数量
//n_w未加入当前货物的重量
//x为一个解集合
//value为未加入当前货物价值的价值
//index当前货物的索引
void get_max_sample(int *w,int *va,int wmax,int n,int n_w,int *x,int value,int index){ int i; if(index==10) { if(maxvalue<value) { for(i=0;i<10;i++) an_x[i]=x[i]; maxvalue=value; } return; } for(i=0;i<2;i++) { x[index]=i; if(n_w+i*w[index]<wmax) { get_max_sample(w,va,wmax,n,n_w+i*w[index],x,value+i*va[index],index+1); } x[index]=0; }}
//求解实例
//get_max_sample(w,va,20,10,0,x,0,0);
//
时间复杂度分析:
由于每一个递归的执行的次数为2次,所以其时间复杂度为:T(2n),所以在n在较小的情况下使用这种方法是可行的,像求解的实例货物数目是10个,T=210=1024,而实际运算的次数肯定是小于这个值.
贪心算法的求解:
利用回溯法求解背包问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。