运用分支定界法(分支限界法)解决01背包问题

2023年8月1日发(作者：)

运⽤分⽀定界法（分⽀限界法）解决01背包问题⾸先初始化总容量capacity = 10、物品总数量number = 4物品信息为【4，40】、【7、42】、【5、25】、【3、12】，分别为重量weight，价值value。解决该题⽬运⽤到的数据结构有：优先队列、⼆叉树、存放物品基本信息的数组这⾥主要就是构建⼆叉树，⼆叉树节点的属性有weight（当前总容量）value（当前总价值）layer（当前层级，⽤来判断是否为叶⼦节点）currentSolution（当前解，算出最⼤价值后，⽅便找出拿了哪些物品）up（上限）left（左孩⼦，取当前物品）right（右孩⼦，不取当前物品）树如下说下各个节点的值是怎么算的这是根节点，所以初始化weight为0、value为0、up为剩余的物品最有可能能取到的最⼤价值。所以up = 当前剩余容量 * (value /weight) = 10 * (40 / 4) = 100。layer层级为0。取第⼀个物品时。weight = 第⼀个物品的weight = 4，value同理。layer层级为1，currentSolution为1（1代表取）up = 当前总价值 + 当前剩余容量 * （第⼆个物品的value / 第⼆个物品的weight）= 40 + (10 - 4) * (42 / 7) = 76不取第⼀个物品。weight = 0，value = 0。layer层级为1，currentSolution为0（0代表取）up = 当前剩余容量 * （第⼆个物品的value / 第⼆个物品的weight）= 10 * (42 / 7) = 60取第⼀个物品、取第⼆个物品。weight = 4 + 第⼆个物品weight = 4 + 7 = 11 > 最⼤容量10。所以该节点不⽤继续计算和保存。取第⼀个物品、不取第⼆个物品。weight = 原来的weight = 4，value = 原来的value = 40，layer层级为2，currentSolution为10up = 当前总价值value + 剩余容量 * （第三个物品的value / 第三个物品的weight）= 40 + (10 - 4) * (25 / 5) = 70取第⼀个物品、不取第⼆个物品、取第三个物品。weight = 已有weight + 第三个物品weight = 4 + 5 = 9，value = 已有value + 第三个物品value = 40 + 25 = 65。layer层级为3，currentSolution为101。up = 当前总价值value + 剩余容量 * （第四个物品的value / 第四个物品的weight）= 65 + (10 - 9) * (12 / 3) = 69取第⼀个物品、不取第⼆个物品、取第三个物品、不取第四个物品。weight = 已有weight = 9，value同理。layer层级为4，currentSolution为1010。因为layer = 物品总数量number = 4所以up = 当前总价值value其它的节点计算⽅式同理。所以根据以上⽅式，最后可以计算出⼀棵⼆叉树。再对其节点进⾏判断。对于左右分⽀，我们并不知道最终答案是在哪个分⽀下⾯，所以两个分⽀都要判断，不过不能太盲⽬。应该有⼀个查找侧重点，因为答案在up值更⼤的节点下⾯可能性更⼤，所以我们有限查找up值较⼤的节点。这⾥就需要⼀个优先队列，把左右节点放⼊到队列中，up值⼤的放在前⾯，优先出队。最后代码（注释就是思路）。⼀共有5个类，Backpack、BinaryTree、ItemInfo、Node、ckage ck;/** *

物品基本信息 */public class ItemInfo { /** *

重量 */ private int weight; /** *

价值 */ private int value; public ItemInfo() {} public ItemInfo(int weight, int value) { = weight; = value; } public int getWeight() { return weight; } public void setWeight(int weight) { = weight; } public int getValue() { return value; } public void setValue(int value) { = value; }}ckage ck;/** *

分⽀定界法，节点属性 *

分⽀定界法，节点属性 */public class Node extends ItemInfo implements Comparable { /** *

层级，⽤来判断是否为叶⼦节点 */ private int layer; /** *

当前解，算出最⼤价值后，⽅便找出拿了哪些物品 */ private String currentSolution; /** *

上限 */ private double up; /** *

取 */ private Node left; /** *

不取 */ private Node right; public Node() {} public int getLayer() { return layer; } public void setLayer(int layer) { = layer; } public String getCurrentSolution() { return currentSolution; } public void setCurrentSolution(String currentSolution) { tSolution = currentSolution; } public double getUp() { return up; } public void setUp(double up) { = up; } public Node getLeft() { return left; } public void setLeft(Node left) { = left; } public Node getRight() { return right; } public void setRight(Node right) { = right; } /** *

优先队列排列⽅式，根据up值⼤⼩来排序 * @param o Node * @return int */ @Override public int compareTo(Object o) { Node node = (Node) o; if(() > ()) { return 1; } else if(() == ()) { return 0; } return -1; }}ckage ck;import .*;/*4 104 407 425 253 12*//** *

背包 */public class Backpack { /** *

总容量 */ private int capacity; /** *

总数量 */ private int number; public BinaryTree binaryTree; /** *

初始化 */ public void initialization() { //

创建根节点 Node head = new Node(); ght(0); ue(0); er(0); rentSolution(""); //

根据每单位质量价值来从⼤到⼩排序 mInfoList().sort((o1, o2) -> { Double a = (double) (ue() / ght()); Double a = (double) (ue() / ght()); Double b = (double) (ue() / ght()); return eTo(a); }); ItemInfo firstNode = mInfoList().get(0); (capacity * (ue() * 1.0 / ght())); kpack(this); //

创建树 dBinaryTree(head, 0); Bound(head); } public void input() { Scanner scanner = new Scanner(); //

物品数量 number = t(); //

背包容量 capacity = t(); mInfoList(new ArrayList<>(number)); for(int i = 0; i < number; i++) { int weight = t(); int value = t(); ItemInfo itemInfo = new ItemInfo(weight, value); mInfoList().add(itemInfo); } } public int getCapacity() { return capacity; } public int getNumber() { return number; } public void setNumber(int number) { = number; } public void setCapacity(int capacity) { ty = capacity; }}ckage ck;import ;import tyQueue;import ;/** *

处理节点树 */public class BinaryTree { /** *

保存所有物品的基本信息，根据每单位质量价值从⼤到⼩来排序 */ private List itemInfoList; /** *

最优解(假如为：1010，代表第⼀个拿，第⼆个不拿，第三个拿，第四个不拿) */ */ private String bestSolution; /** *

最优值 */ private int max; private Backpack backpack; /** *

判断节点是否符合要求 * @param node

树的当前节点 * @param upPriorityQueue

优先队列 */ private void judgementNode(Node node, Queue upPriorityQueue) { if(node == null) { return; } //

当前节点对应的总重量超过背包最⼤容量 ||

当前节点最可能的最⼤价值up⼩于已知的价值 // ght() > acity()这个判断其实是多余的。。 if(ght() > acity() || () < max) { return; } //

当前的节点对应的层级是否⼩于总数量 if(er() < ber()) { (node); } else { //

更新最优价值 max = ue(); //

更新最优解 bestSolution = rentSolution(); } } /** *

分⽀界定 * @param node

根节点 */ public void branchBound(Node node) { //

使⽤优先队列，根据节点的up值，优先权由⼤到⼩ Queue upPriorityQueue = new PriorityQueue<>(); (node); while(!y()) { node = (); //

如果队列中第⼀个节点的up值⼩于最优价值，则就没必要继续遍历队列。 if(() <= max) { break; } judgementNode(t(), upPriorityQueue); judgementNode(ht(), upPriorityQueue); } } /** *

创建⼆叉树 * @param node

当前节点 * @param index

物品List对应下标 */ public void createdBinaryTree(Node node, int index) { if(index >= ber()) { return; } //

获取当前物品信息 ItemInfo currentItem = (index); if(t() == null) { Node leftNode = new Node(); //

因为是左节点，代表拿。被拿当前物品价值+已有的物品总价值 //

因为是左节点，代表拿。被拿当前物品价值+已有的物品总价值 ue(ue() + ue()); //

被拿当前物品重量+已有的物品总重量 ght(ght() + ght()); //

设置层级index从0开始，0代表根节点的层级 er(index + 1); //

算出剩余容量 int surplus = acity() - ght(); //

这⾥进⾏减去枝，如果剩余容量⼩于0说明当前物品⽆法放⼊ if(surplus >= 0) { //

如果不是最后⼀层，index在这⾥，可以理解为层级 if(index + 1 < ()) { //

当前物品的下⼀个物品 ItemInfo nextNode = (index + 1); //

求出剩余物品的最⼤up值，下⼀个物品每单位容量最⼤价值*剩余容量 int up = surplus * (ue() / ght()); //

是否为根节点 if(index == 0) { //

根节点只需要获取当前物品的价值+up (up + ue()); } else { //

⾮根节点需要获取当前总价值+up (up + ue()); } } else { //

最后⼀层，其实就是最后⼀个物品，对应最后⼀层的节点的up就是当前节点的value (ue()); } //

更新解过程，1代表left，即拿取 rentSolution(rentSolution() + 1); t(leftNode); createdBinaryTree(t(), index + 1); } } if(ht() == null) { Node rightNode = new Node(); //

因为是右节点，代表不拿。所以直接设置为已有的物品总价值 ue(ue()); ght(ght()); er(index + 1); int surplus = acity() - ght(); if(surplus >= 0) { if(index + 1 < ()) { ItemInfo nextNode = (index + 1); int up = surplus * (ue() / ght()); if(index == 0) { (up); } else { (up + ue()); } } else { (ue()); } rentSolution(rentSolution() + 0); ht(rightNode); createdBinaryTree(ht(), index + 1); } } } /** *

遍历树 * @param node

节点 */ public void preOrderBinaryTree(Node node) { if(node != null) { if(node != null) { n(ng()); preOrderBinaryTree(t()); preOrderBinaryTree(ht()); } } public List getItemInfoList() { return itemInfoList; } public void setItemInfoList(List itemInfoList) { foList = itemInfoList; } public String getBestSolution() { return bestSolution; } public void setBestSolution(String bestSolution) { lution = bestSolution; } public int getMax() { return max; } public void setMax(int max) { = max; } public Backpack getBackpack() { return backpack; } public void setBackpack(Backpack backpack) { ck = backpack; }}ckage ck;/** *

运⽤分⽀定界法解决背包问题 */public class Main { public static void main(String[] args) { Backpack backpack = new Backpack(); Tree = new BinaryTree(); (); lization(); n("最⼤价值为：" + ()); String bestSolution = tSolution(); n("拿取的物品为："); for(int i = 0; i < (); i++) { if((i) != '0') { ItemInfo itemInfo = mInfoList().get(i); n("[" + ght() + " " + ue() + "]"); } } }}测试4 104 407 425 253 12最⼤价值为：65拿取的物品为：[4 40][5 25]

2023年8月1日发(作者：)

运⽤分⽀定界法（分⽀限界法）解决01背包问题⾸先初始化总容量capacity = 10、物品总数量number = 4物品信息为【4，40】、【7、42】、【5、25】、【3、12】，分别为重量weight，价值value。解决该题⽬运⽤到的数据结构有：优先队列、⼆叉树、存放物品基本信息的数组这⾥主要就是构建⼆叉树，⼆叉树节点的属性有weight（当前总容量）value（当前总价值）layer（当前层级，⽤来判断是否为叶⼦节点）currentSolution（当前解，算出最⼤价值后，⽅便找出拿了哪些物品）up（上限）left（左孩⼦，取当前物品）right（右孩⼦，不取当前物品）树如下说下各个节点的值是怎么算的这是根节点，所以初始化weight为0、value为0、up为剩余的物品最有可能能取到的最⼤价值。所以up = 当前剩余容量 * (value /weight) = 10 * (40 / 4) = 100。layer层级为0。取第⼀个物品时。weight = 第⼀个物品的weight = 4，value同理。layer层级为1，currentSolution为1（1代表取）up = 当前总价值 + 当前剩余容量 * （第⼆个物品的value / 第⼆个物品的weight）= 40 + (10 - 4) * (42 / 7) = 76不取第⼀个物品。weight = 0，value = 0。layer层级为1，currentSolution为0（0代表取）up = 当前剩余容量 * （第⼆个物品的value / 第⼆个物品的weight）= 10 * (42 / 7) = 60取第⼀个物品、取第⼆个物品。weight = 4 + 第⼆个物品weight = 4 + 7 = 11 > 最⼤容量10。所以该节点不⽤继续计算和保存。取第⼀个物品、不取第⼆个物品。weight = 原来的weight = 4，value = 原来的value = 40，layer层级为2，currentSolution为10up = 当前总价值value + 剩余容量 * （第三个物品的value / 第三个物品的weight）= 40 + (10 - 4) * (25 / 5) = 70取第⼀个物品、不取第⼆个物品、取第三个物品。weight = 已有weight + 第三个物品weight = 4 + 5 = 9，value = 已有value + 第三个物品value = 40 + 25 = 65。layer层级为3，currentSolution为101。up = 当前总价值value + 剩余容量 * （第四个物品的value / 第四个物品的weight）= 65 + (10 - 9) * (12 / 3) = 69取第⼀个物品、不取第⼆个物品、取第三个物品、不取第四个物品。weight = 已有weight = 9，value同理。layer层级为4，currentSolution为1010。因为layer = 物品总数量number = 4所以up = 当前总价值value其它的节点计算⽅式同理。所以根据以上⽅式，最后可以计算出⼀棵⼆叉树。再对其节点进⾏判断。对于左右分⽀，我们并不知道最终答案是在哪个分⽀下⾯，所以两个分⽀都要判断，不过不能太盲⽬。应该有⼀个查找侧重点，因为答案在up值更⼤的节点下⾯可能性更⼤，所以我们有限查找up值较⼤的节点。这⾥就需要⼀个优先队列，把左右节点放⼊到队列中，up值⼤的放在前⾯，优先出队。最后代码（注释就是思路）。⼀共有5个类，Backpack、BinaryTree、ItemInfo、Node、ckage ck;/** *

物品基本信息 */public class ItemInfo { /** *

重量 */ private int weight; /** *

价值 */ private int value; public ItemInfo() {} public ItemInfo(int weight, int value) { = weight; = value; } public int getWeight() { return weight; } public void setWeight(int weight) { = weight; } public int getValue() { return value; } public void setValue(int value) { = value; }}ckage ck;/** *

分⽀定界法，节点属性 *

分⽀定界法，节点属性 */public class Node extends ItemInfo implements Comparable { /** *

层级，⽤来判断是否为叶⼦节点 */ private int layer; /** *

当前解，算出最⼤价值后，⽅便找出拿了哪些物品 */ private String currentSolution; /** *

上限 */ private double up; /** *

取 */ private Node left; /** *

不取 */ private Node right; public Node() {} public int getLayer() { return layer; } public void setLayer(int layer) { = layer; } public String getCurrentSolution() { return currentSolution; } public void setCurrentSolution(String currentSolution) { tSolution = currentSolution; } public double getUp() { return up; } public void setUp(double up) { = up; } public Node getLeft() { return left; } public void setLeft(Node left) { = left; } public Node getRight() { return right; } public void setRight(Node right) { = right; } /** *

优先队列排列⽅式，根据up值⼤⼩来排序 * @param o Node * @return int */ @Override public int compareTo(Object o) { Node node = (Node) o; if(() > ()) { return 1; } else if(() == ()) { return 0; } return -1; }}ckage ck;import .*;/*4 104 407 425 253 12*//** *

背包 */public class Backpack { /** *

总容量 */ private int capacity; /** *

总数量 */ private int number; public BinaryTree binaryTree; /** *

初始化 */ public void initialization() { //

创建根节点 Node head = new Node(); ght(0); ue(0); er(0); rentSolution(""); //

根据每单位质量价值来从⼤到⼩排序 mInfoList().sort((o1, o2) -> { Double a = (double) (ue() / ght()); Double a = (double) (ue() / ght()); Double b = (double) (ue() / ght()); return eTo(a); }); ItemInfo firstNode = mInfoList().get(0); (capacity * (ue() * 1.0 / ght())); kpack(this); //

创建树 dBinaryTree(head, 0); Bound(head); } public void input() { Scanner scanner = new Scanner(); //

物品数量 number = t(); //

背包容量 capacity = t(); mInfoList(new ArrayList<>(number)); for(int i = 0; i < number; i++) { int weight = t(); int value = t(); ItemInfo itemInfo = new ItemInfo(weight, value); mInfoList().add(itemInfo); } } public int getCapacity() { return capacity; } public int getNumber() { return number; } public void setNumber(int number) { = number; } public void setCapacity(int capacity) { ty = capacity; }}ckage ck;import ;import tyQueue;import ;/** *

处理节点树 */public class BinaryTree { /** *

保存所有物品的基本信息，根据每单位质量价值从⼤到⼩来排序 */ private List itemInfoList; /** *

最优解(假如为：1010，代表第⼀个拿，第⼆个不拿，第三个拿，第四个不拿) */ */ private String bestSolution; /** *

最优值 */ private int max; private Backpack backpack; /** *

判断节点是否符合要求 * @param node

树的当前节点 * @param upPriorityQueue

优先队列 */ private void judgementNode(Node node, Queue upPriorityQueue) { if(node == null) { return; } //

当前节点对应的总重量超过背包最⼤容量 ||

当前节点最可能的最⼤价值up⼩于已知的价值 // ght() > acity()这个判断其实是多余的。。 if(ght() > acity() || () < max) { return; } //

当前的节点对应的层级是否⼩于总数量 if(er() < ber()) { (node); } else { //

更新最优价值 max = ue(); //

更新最优解 bestSolution = rentSolution(); } } /** *

分⽀界定 * @param node

根节点 */ public void branchBound(Node node) { //

使⽤优先队列，根据节点的up值，优先权由⼤到⼩ Queue upPriorityQueue = new PriorityQueue<>(); (node); while(!y()) { node = (); //

如果队列中第⼀个节点的up值⼩于最优价值，则就没必要继续遍历队列。 if(() <= max) { break; } judgementNode(t(), upPriorityQueue); judgementNode(ht(), upPriorityQueue); } } /** *

创建⼆叉树 * @param node

当前节点 * @param index

物品List对应下标 */ public void createdBinaryTree(Node node, int index) { if(index >= ber()) { return; } //

获取当前物品信息 ItemInfo currentItem = (index); if(t() == null) { Node leftNode = new Node(); //

因为是左节点，代表拿。被拿当前物品价值+已有的物品总价值 //

因为是左节点，代表拿。被拿当前物品价值+已有的物品总价值 ue(ue() + ue()); //

被拿当前物品重量+已有的物品总重量 ght(ght() + ght()); //

设置层级index从0开始，0代表根节点的层级 er(index + 1); //

算出剩余容量 int surplus = acity() - ght(); //

这⾥进⾏减去枝，如果剩余容量⼩于0说明当前物品⽆法放⼊ if(surplus >= 0) { //

如果不是最后⼀层，index在这⾥，可以理解为层级 if(index + 1 < ()) { //

当前物品的下⼀个物品 ItemInfo nextNode = (index + 1); //

求出剩余物品的最⼤up值，下⼀个物品每单位容量最⼤价值*剩余容量 int up = surplus * (ue() / ght()); //

是否为根节点 if(index == 0) { //

根节点只需要获取当前物品的价值+up (up + ue()); } else { //

⾮根节点需要获取当前总价值+up (up + ue()); } } else { //

最后⼀层，其实就是最后⼀个物品，对应最后⼀层的节点的up就是当前节点的value (ue()); } //

更新解过程，1代表left，即拿取 rentSolution(rentSolution() + 1); t(leftNode); createdBinaryTree(t(), index + 1); } } if(ht() == null) { Node rightNode = new Node(); //

因为是右节点，代表不拿。所以直接设置为已有的物品总价值 ue(ue()); ght(ght()); er(index + 1); int surplus = acity() - ght(); if(surplus >= 0) { if(index + 1 < ()) { ItemInfo nextNode = (index + 1); int up = surplus * (ue() / ght()); if(index == 0) { (up); } else { (up + ue()); } } else { (ue()); } rentSolution(rentSolution() + 0); ht(rightNode); createdBinaryTree(ht(), index + 1); } } } /** *

遍历树 * @param node

节点 */ public void preOrderBinaryTree(Node node) { if(node != null) { if(node != null) { n(ng()); preOrderBinaryTree(t()); preOrderBinaryTree(ht()); } } public List getItemInfoList() { return itemInfoList; } public void setItemInfoList(List itemInfoList) { foList = itemInfoList; } public String getBestSolution() { return bestSolution; } public void setBestSolution(String bestSolution) { lution = bestSolution; } public int getMax() { return max; } public void setMax(int max) { = max; } public Backpack getBackpack() { return backpack; } public void setBackpack(Backpack backpack) { ck = backpack; }}ckage ck;/** *

运⽤分⽀定界法解决背包问题 */public class Main { public static void main(String[] args) { Backpack backpack = new Backpack(); Tree = new BinaryTree(); (); lization(); n("最⼤价值为：" + ()); String bestSolution = tSolution(); n("拿取的物品为："); for(int i = 0; i < (); i++) { if((i) != '0') { ItemInfo itemInfo = mInfoList().get(i); n("[" + ght() + " " + ue() + "]"); } } }}测试4 104 407 425 253 12最⼤价值为：65拿取的物品为：[4 40][5 25]