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

01背包问题（回溯法）　　回溯法是⼀个既带有系统性⼜带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索⾄解空间树的任意⼀结点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的⼦树搜索，逐层向其祖先结点回溯；否则 ，进⼊该⼦树，继续按深度优先策略搜索。

问题的解空间⽤回溯法解问题时，应明确定义问题的解空间。问题的解空间⾄少包含问题的⼀个(最优)解。对于 n=3 时的 0/1 背包问题，可⽤⼀棵完全⼆叉树表⽰解空间，如图所⽰：

求解步骤1)针对所给问题，定义问题的解空间；2)确定易于搜索的解空间结构；3)以深度优先⽅式搜索解空间，并在搜索过程中⽤剪枝函数避免⽆效搜索。常⽤的剪枝函数：⽤约束函数在扩展结点处剪去不满⾜约束的⼦树；⽤限界函数剪去得不到最优解的⼦树。回溯法对解空间做深度优先搜索时，有递归回溯和迭代回溯（⾮递归）两种⽅法，但⼀般情况下⽤递归⽅法实现回溯法。

算法描述　　解 0/1 背包问题的回溯法在搜索解空间树时，只要其左⼉⼦结点是⼀个可⾏结点，搜索就进⼊其左⼦树。当右⼦树中有可能包含最优解时才进⼊右⼦树搜索。否则将右⼦树剪去。

代码：public class Knapsack_Problem01 { double m=100; //背包最⼤容量 int n=5; //物品的个数 int[] w = {10,20,30,40,50}; //第i个物品的重量 int[] v = {20,30,65,40,60}; //第i个物品的价值

int[] a = new int[n]; //记录在树中的移动路径,为1的时候表⽰选择该组数据，为0的表⽰不选择该组数据 int maxvalue = 0; //背包的最⼤权重值 public static void main(String[] args) { Knapsack_Problem01 p = new Knapsack_Problem01(); (0); } public void Search(int i) //i表⽰递归深度 { if(i>=n) { CheckMax(); } else { a[i] = 0; Search(i+1); a[i] = 1; Search(i+1); } } public void CheckMax() { int weight = 0; int value = 0; for(int i=0;i= maxvalue) { maxvalue = value; ("最⼤价值是：" + maxvalue +" "); ("所选取的物品为(1代表选中，0代表不选中)： "); for(int j=0;j

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

01背包问题（回溯法）　　回溯法是⼀个既带有系统性⼜带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索⾄解空间树的任意⼀结点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的⼦树搜索，逐层向其祖先结点回溯；否则 ，进⼊该⼦树，继续按深度优先策略搜索。

问题的解空间⽤回溯法解问题时，应明确定义问题的解空间。问题的解空间⾄少包含问题的⼀个(最优)解。对于 n=3 时的 0/1 背包问题，可⽤⼀棵完全⼆叉树表⽰解空间，如图所⽰：

求解步骤1)针对所给问题，定义问题的解空间；2)确定易于搜索的解空间结构；3)以深度优先⽅式搜索解空间，并在搜索过程中⽤剪枝函数避免⽆效搜索。常⽤的剪枝函数：⽤约束函数在扩展结点处剪去不满⾜约束的⼦树；⽤限界函数剪去得不到最优解的⼦树。回溯法对解空间做深度优先搜索时，有递归回溯和迭代回溯（⾮递归）两种⽅法，但⼀般情况下⽤递归⽅法实现回溯法。

算法描述　　解 0/1 背包问题的回溯法在搜索解空间树时，只要其左⼉⼦结点是⼀个可⾏结点，搜索就进⼊其左⼦树。当右⼦树中有可能包含最优解时才进⼊右⼦树搜索。否则将右⼦树剪去。

代码：public class Knapsack_Problem01 { double m=100; //背包最⼤容量 int n=5; //物品的个数 int[] w = {10,20,30,40,50}; //第i个物品的重量 int[] v = {20,30,65,40,60}; //第i个物品的价值

int[] a = new int[n]; //记录在树中的移动路径,为1的时候表⽰选择该组数据，为0的表⽰不选择该组数据 int maxvalue = 0; //背包的最⼤权重值 public static void main(String[] args) { Knapsack_Problem01 p = new Knapsack_Problem01(); (0); } public void Search(int i) //i表⽰递归深度 { if(i>=n) { CheckMax(); } else { a[i] = 0; Search(i+1); a[i] = 1; Search(i+1); } } public void CheckMax() { int weight = 0; int value = 0; for(int i=0;i= maxvalue) { maxvalue = value; ("最⼤价值是：" + maxvalue +" "); ("所选取的物品为(1代表选中，0代表不选中)： "); for(int j=0;j