分支限界法解0-1背包问题时的解空间树是（）
回答
共1条回复-
package algorith;import java.util.ArrayList;import java.util.Collections;import java.util.List;/**** @author cjb** 背包问题：4种物品，重量wi与价值vi分别为* v1=1,v2=3,v3=5,v4=9;* w1=2,w2=3,w3=4,w4=7;* 背包重量限制为10;** max x1+3x2+5x3+9x4 ;* 2x1+3x2+4x3+7x4**/public class BagProblem {public static int[] value = { 1, 3, 5, 9 };public static int[] weight = { 2, 3, 4, 7 };public static List goodsList = new ArrayList();public static float maxValue = 0;public static void main(String[] args) {for (int i = 0; i goodsList.add(new Goods(value[i], weight[i]));}Collections.sort(goodsList);Node root = new Node(0, 0, 0, 10);travel(root);System.out.println(maxValue);}private static void travel(Node root) {if (root.goodsNo == goodsList.size()) {return;} else {if (root.bagValue > maxValue) {maxValue = root.bagValue;}for (int i = (int) root.remainedWeight / goodsList.get(root.goodsNo).w; i >= 0; i--) {if (root.remainedWeight >= goodsList.get(root.goodsNo).w * i && evaluate(root)) {Node child = new Node(root.goodsNo + 1, i, root.bagValue + goodsList.get(root.goodsNo).v * i,root.remainedWeight - goodsList.get(root.goodsNo).w * i);travel(child);}}}}private static boolean evaluate(Node root) {float v = (float) goodsList.get(root.goodsNo).v ;float w = (float) goodsList.get(root.goodsNo).w;return root.bagValue + root.remainedWeight * v / w > maxValue ? true : false;}}===========================================================package algorith;public class Node {// 物品编号int goodsNo;// 父结点消耗num个对应物品后扩展出来的孩子结点，同时用于标示第几个孩子int parentGoodsNum;// 袋子里的物品价值float bagValue;// 袋子剩余可装的物品重量float remainedWeight;public Node(int goodsNo, int parentGoodsNum, float bagValue, float remainedWeight) {this.goodsNo = goodsNo;this.parentGoodsNum = parentGoodsNum;this.bagValue = bagValue;this.remainedWeight = remainedWeight;}public Node() {}}===================================================package algorith;public class Goods implements Comparable {int v;int w;public Goods(int v, int w) {this.v = v;this.w = w;}//扩展Comparable接口，必须实现的回调方法，明确物品排序时如何比大小（这里用逆序），给排序算法自动调用@Overridepublic int compareTo(Goods o) {// TODO Auto-generated method stubfloat vv=v;float ww=w;float ov=o.v;float ow=o.w;if (vv / ww > ov / ow) {return -1;} else if (vv / ww == ov / ow) {return 0;} else {return 1;}}}