分支限定法的具体实现问题.doc

实验三 用分支限界法实现0/1背包问题实验目的 1、用分支限界法实现0/1背包问题 2、学会用java实现算法代码实验原理分枝限界是另一种系统地搜索解空间的方法，它与回溯法的主要区别在于对E-节点的扩充方式。每个活节点有且仅有一次机会变成E-节点。当一个节点变为E-节点时，则生成从该节点移动一步即可到达的所有新节点。在生成的节点中，抛弃那些不可能导出（最优）可行解的节点，其余节点加入活节点表，然后从表中选择一个节点作为下一个E-节点。从活节点表中取出所选择的节点并进行扩充，直到找到解或活动表为空，扩充过程才结束。现要求给出一个具体的0/1背包问题，并用分支限界法求解之。实验程序 import java.util.*;public class BBKnapsack int capactity;/ 背包重量int n; / 物品总数int weight;/ 物品重量数组int value;/ 物品价值数组int curWeight; / 当前重量int curValue; / 当前价值int bestx; / 最优解MaxHeap maxHeap = new MaxHeap();/ 活节点优先队列/ 计算节点所对应的节点的上界private int bound(int i) int cleft = capactity - curWeight;int b = curValue;/ 以物品单位重量价值递减装填剩余容量while (i = n & weighti = cleft) cleft -= weighti;b += valuei;i+;/ 装填剩余容量装满背包if (i = n) b += valuei / weighti * cleft;return b;/ 添加新的活节点到子集树和优先队列中private void addLiveNode(int upperProfit, int pp, int ww,int level, BBnode parent, boolean leftChild) BBnode b = new BBnode(parent, leftChild);HeapNode node = new HeapNode(b, upperProfit, pp, ww, level);maxHeap.put(node);/ 优先队列式分支界限法private int bbKnapsack() BBnode enode = null;int i = 1;int bestp = 0;int up = bound(1);while (i != n + 1) int wt = curWeight + weighti;/ 检查当前扩展节点的左儿子节点if (wt bestp) bestp = curValue + valuei;addLiveNode(up, curValue + valuei, curWeight + weighti,i + 1, enode, true);up = bound(i + 1);/ 检查当前扩展节点的右儿子节点if (up = bestp) addLiveNode(up, curValue, curWeight, i + 1, enode, false);HeapNode node = maxHeap.removeMax();enode = node.liveNode;curWeight = node.weight;curValue = fit;up = node.upperProfit;i = node.level;/ 构造当前最优解for (int j = n; j 0; j-) bestxj = (enode.leftChild) ? 1 : 0;enode = enode.parent;return curValue;public int knapsack(int pp, int ww, int cc, int xx) capactity = cc;n = pp.length - 1;/ n = pp.lengthElement q = new Elementn;int ws = 0;int ps = 0;for (int i = 0; i n; i+) qi = new Element(i + 1, ppi / wwi);ps += ppi;ws += wwi;if (ws = capactity) for (int i = 1; i = n; i+) xxi = 1;return ps;/ 依单位重量价值排序Arrays.sort(q, new ElemComparator();value = new intn + 1;weight = new intn + 1;for (int i = 1; i = n; i+) valuei = ppqi - 1.id - 1;weighti = wwqi - 1.id - 1;curWeight = 0;curValue = 0;bestx = new intn + 1;maxHeap = new MaxHeap();/ 调用bbKnapsack求问题的最优解int maxp = bbKnapsack();for (int i = 1; i = n; i+) xxqn - i.id = bestxi;return maxp;public static void main(String arg) throws Exception int capacity = 0;int pp;int ww;int choice;int bestP = 0;String str = 最优解为：;FileOperation f1 = new FileOperation();Vector v1 = f1.loadFile(D:/物品重量.txt);ww = new intv1.size() - 1;for (int i = 0; i v1.size() - 1; i+) wwi = v1.get(i);capacity = v1.get(v1.size() - 1);FileOperation f2 = new FileOperation();Vector v2 = f2.loadFile(D:/物品价值.txt);pp = new intv2.size();for (int i = 0; i v2.size(); i+) ppi = v2.get(i);choice = new intpp.length;BBKnapsack bbKnapsack = new BBKnapsack();bestP = bbKnapsack.knapsack(pp, ww, capacity, choice);str += bestP + 各物品被装入的情况为（0代表不被装入，1代表被装入）：;for (int i = 0; i choice.length; i+) str += + choicei;f1.saveFile(D:/分支界限法求背包问题输出文件.txt, str);import java.util.Comparator;public class HeapComparator implements Comparatorpublic int compare(Object object1, Object object2) HeapNode heapNode1 = (HeapNode)object1;HeapNode heapNode2 = (HeapNode)object2;if (heapNode1.upperProfit heapNode2.upperProfit) return 1; else return 0;public class HeapNode BBnode liveNode; / 活节点int upperProfit; / 节点价值上限int profit; / 节点所对应的价值int weight; / 节点所对应的重量int level; / 活节点在子集树中所处的层次序号/ 构造方法public HeapNode(BBnode liveNode, int upperProfit, int profit,int weight, int level) this.liveNode = liveNode;this.upperProfit = upperProfit;fit = profit;this.weight = weight;this.level = level;import java.util.ArrayList;import java.util.Collections;import java.util.List;public class MaxHeap /堆节点容器private List heap=new ArrayList();public void put(HeapNode heapNode)heap.add(heapNode); public HeapNode removeMax() Collections.sort(heap, new HeapComparator(); HeapNode maxNode=null; if(!heap.isEmpty() maxNode=heap.get(0); heap.remove(maxNode); return maxNode;public class BBn