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

01背包暴⼒解法，giegie不温柔了0/1背包问题有 n 件物品，第 i 件的重量和价值分别是 wi 和 vi 。要将这 n 件物品的⼀部分装⼊容量为c 的背包中，要求每件物品或整个装⼊或不装⼊。0/1背包问题就是要给出装包算法，使得装⼊背包的物品的总价值最⼤。本节采⽤回溯⽅法求解，选择出满⾜⽬标函数极⼤化和重量要求的⼀个⼦集。0/1⼀般使⽤动态规划来写的，这⾥介绍的是暴⼒的回溯⽅法。思路解析解空间树：回溯⽅法的第⼀步就是确定解空间树，对于⼀个物品有要和不要两种选择。所以这是⼀颗⼆叉树。我们要得到的是⼀个解向量X={1，0，1，0，0…}，表⽰选取那些节点。怎么做呢？1.对于效益数组V和重量数组W，根据wi/vi（性价⽐）来排序。我们先把性价⽐⾼的放进去。 2.可是保证先放性价⽐最⾼的就能实现是最优结果吗？看看下⾯这⾥例⼦ 因此，对性价⽐优先的⽅法做出改进。 即，加⼊判断： 如果在不选本物品，⽽把后⾯的物品尽可能的装⼊的情况下，价值⽐最⼤收益⼤，就继续递归 如果829import Arrays;public class Bag0_1 { public static void main(String[] args) { int[] val ={60,100,120}; int[] vol ={10,20,30}; bag b=new bag(50,val,vol); (); (0,0,50); n(+" "+ng()); }}class bag{/*** *

属性： 1.容量C 2.价值数组val 3.体积数组vol 4.解向量X 5.最⼤效益fc 6.解向量长度n *

⽅法： 1.构造⽅法 2.性价⽐排序 3.回溯 * getIn(t,cv,r) * t:当前步骤 * cv：当前价值 * cw:剩余容量 */ public int C,fv=-1,n; public int[] Val,Vol; public int[] X,BC; public bag(int c, int[] val, int[] vol) { C = c; Val = val; Vol = vol;293637383946474849565758596667686976777879808182 Vol = vol; X=new int[]; n=; } public int[] sort(){ int[] X=new int[]; for (int i=0;i<=-1;i++){ X[i]=Val[i]/Vol[i]; }//

对X做⼀个冒泡排序 for (int i=-1;i>=0;i--){ for (int j=0;j=n&&cv>fv){ fv=cv; BC=X; } else if (tfv){ X[t]=0; getIn(t+1,cv,cw); } } } public double Rest(int t,int rc){ double rv=0; for (;t

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

01背包暴⼒解法，giegie不温柔了0/1背包问题有 n 件物品，第 i 件的重量和价值分别是 wi 和 vi 。要将这 n 件物品的⼀部分装⼊容量为c 的背包中，要求每件物品或整个装⼊或不装⼊。0/1背包问题就是要给出装包算法，使得装⼊背包的物品的总价值最⼤。本节采⽤回溯⽅法求解，选择出满⾜⽬标函数极⼤化和重量要求的⼀个⼦集。0/1⼀般使⽤动态规划来写的，这⾥介绍的是暴⼒的回溯⽅法。思路解析解空间树：回溯⽅法的第⼀步就是确定解空间树，对于⼀个物品有要和不要两种选择。所以这是⼀颗⼆叉树。我们要得到的是⼀个解向量X={1，0，1，0，0…}，表⽰选取那些节点。怎么做呢？1.对于效益数组V和重量数组W，根据wi/vi（性价⽐）来排序。我们先把性价⽐⾼的放进去。 2.可是保证先放性价⽐最⾼的就能实现是最优结果吗？看看下⾯这⾥例⼦ 因此，对性价⽐优先的⽅法做出改进。 即，加⼊判断： 如果在不选本物品，⽽把后⾯的物品尽可能的装⼊的情况下，价值⽐最⼤收益⼤，就继续递归 如果829import Arrays;public class Bag0_1 { public static void main(String[] args) { int[] val ={60,100,120}; int[] vol ={10,20,30}; bag b=new bag(50,val,vol); (); (0,0,50); n(+" "+ng()); }}class bag{/*** *

属性： 1.容量C 2.价值数组val 3.体积数组vol 4.解向量X 5.最⼤效益fc 6.解向量长度n *

⽅法： 1.构造⽅法 2.性价⽐排序 3.回溯 * getIn(t,cv,r) * t:当前步骤 * cv：当前价值 * cw:剩余容量 */ public int C,fv=-1,n; public int[] Val,Vol; public int[] X,BC; public bag(int c, int[] val, int[] vol) { C = c; Val = val; Vol = vol;293637383946474849565758596667686976777879808182 Vol = vol; X=new int[]; n=; } public int[] sort(){ int[] X=new int[]; for (int i=0;i<=-1;i++){ X[i]=Val[i]/Vol[i]; }//

对X做⼀个冒泡排序 for (int i=-1;i>=0;i--){ for (int j=0;j=n&&cv>fv){ fv=cv; BC=X; } else if (tfv){ X[t]=0; getIn(t+1,cv,cw); } } } public double Rest(int t,int rc){ double rv=0; for (;t