网站的结构类型,松江新城投资建设集团发展有限公司网站,骨科免费咨询,惠州个人做网站联系人背包问题九讲我发现背包问题既棘手又有趣。 我敢肯定#xff0c;如果您正在访问此页面#xff0c;您已经知道了问题说明#xff0c;但是只是为了完成本章#xff1a; 问题#xff1a; 给定一个最大容量为W和N的背包#xff0c;每个背包都有自己的值和重量#xff0c;将… 背包问题九讲 我发现背包问题既棘手又有趣。 我敢肯定如果您正在访问此页面您已经知道了问题说明但是只是为了完成本章 问题 给定一个最大容量为W和N的背包每个背包都有自己的值和重量将它们放入背包中使最终内容物具有最大值。 kes 链接到Wiki中的问题页面 这是解释问题的一般方法-考虑一个小偷进入家中抢劫他背着背包。 家里有固定数量的物品-每个物品都有自己的重量和价值-珠宝首饰重量和重量比桌子高价值少但重量重。 为了给火上加油小偷有一个老式的背包容量有限。 显然他不能将桌子分成两半也不能将珠宝分成3/4分。 他要么接受要么离开。 范例 Knapsack Max weight : W 10 (units)Total items : N 4Values of items : v[] {10, 40, 30, 50}Weight of items : w[] {5, 4, 6, 3} 粗略看一下示例数据可知在最大权重为10的情况下我们可以容纳的最大值为50 40 90权重为7。 方法 最佳解决方法是使用动态编程-解决较小的背包问题然后将其扩展为较大的问题。 让我们构建一个名为V值数组的Item x权重数组 V[N][W] 4 rows * 10 columns 此矩阵中的每个值代表一个较小的背包问题。 基本案例1 让我们以第0列为例。 这仅意味着背包的容量为0。 你能在他们身上抱什么 没有。 因此让我们用0填充它们。 基本情况2 让我们以0行为例。 这仅表示房子中没有物品。 如果没有物品您在背包里会做什么 没事了 全零。 解 现在让我们开始逐行填充数组。 第1行和第1列是什么意思 给定第一个项目行您能否将其容纳在容量为1列的背包中。 不。 第一项的权重为5。因此让我们填写0。实际上直到到达第5列权重5我们才能填写任何内容。 一旦我们到达第一行的第5列代表权重5这意味着我们可以容纳第1项。让我们在此处填写10请记住这是一个Value数组 继续对于权重6第6列我们是否可以容纳剩余重量为1重量–该项目的重量 6 – 5的任何其他东西。 嘿记住我们在第一个项目上。 因此从直觉上讲该行的其余部分也将是相同的值因为我们无法为已获得的额外重量添加任何其他项目。 因此当我们到达第三行的第4列时会发生下一个有趣的事情。 当前的跑步重量为4。 我们应检查以下情况。 我们可以容纳项目2 –是的我们可以。 项目2的权重为4。 如果没有第2项当前重量的值是否会更高 –检查上一行是否具有相同的重量。 不。 前一行*的内容为0因为我们无法容纳重量为4的商品1。 我们是否可以容纳两个重量相同的物品以使价值最大化 - 不。 减去Item2的权重后的剩余权重为0。 为什么要上一行 仅仅是因为权重为4的前一行本身是一个较小的背包解决方案它给出了该权重在该点之前可以累积的最大值遍历所有项目。 举例来说 当前项目的值 40 当前商品的重量 4 剩下的权重 4 – 4 0 检查上面的行如果是项目1则检查上面的项目如果其余的行则检查累积最大值。 对于剩余重量0我们是否可以容纳项目1 简而言之对于给定的重量上一行是否有任何值 计算如下 不带此项取相同重量的最大值 previous row, same weight 0 V[item-1][weight] 取当前商品的价值我们可以用剩余重量容纳的价值 Value of current itemvalue in previous row with weight 4 (total weight until now (4) - weight of the current item (4)) val[item-1] V[item-1][weight-wt[item-1]] 两者之间的最大值为400和40。 下一个也是最重要的事件发生在第9列和第2行。这意味着我们的权重为9并且有两项。 查看示例数据我们可以容纳前两个项目。 在这里我们考虑几件事 1. The value of the current item 40
2. The weight of the current item 4
3. The weight that is left over 9 - 4 5
4. Check the row above. At the remaining weight 5, are we able to accommodate Item 1. 因此计算公式为 不带此项取相同重量的最大值 previous row, same weight 10 取当前商品的价值我们可以用剩余重量累计的价值 Value of current item (40)value in previous row with weight 5 (total weight until now (9) - weight of the current item (4)) 10 10比50 50。 解决所有这些较小的问题后我们只需要返回权重为10的V [N] [W] –项目4的值 复杂 分析解决方案的复杂性非常简单。 我们只是在N ONW的循环中有一个W循环 实现方式 这是Java中的强制性实现代码 class Knapsack {public static void main(String[] args) throws Exception {int val[] {10, 40, 30, 50};int wt[] {5, 4, 6, 3};int W 10;System.out.println(knapsack(val, wt, W));}public static int knapsack(int val[], int wt[], int W) {//Get the total number of items. //Could be wt.length or val.length. Doesnt matterint N wt.length; //Create a matrix. //Items are in rows and weight at in columns 1 on each sideint[][] V new int[N 1][W 1]; //What if the knapsacks capacity is 0 - Set//all columns at row 0 to be 0for (int col 0; col W; col) {V[0][col] 0;}//What if there are no items at home. //Fill the first row with 0for (int row 0; row N; row) {V[row][0] 0;}for (int item1;itemN;item){//Lets fill the values row by rowfor (int weight1;weightW;weight){//Is the current items weight less//than or equal to running weightif (wt[item-1]weight){//Given a weight, check if the value of the current
//item value of the item that we could afford
//with the remaining weight is greater than the value
//without the current item itselfV[item][weight]Math.max (val[item-1]V[item-1][weight-wt[item-1]], V[item-1][weight]);}else {
//If the current items weight is more than the
//running weight, just carry forward the value
//without the current itemV[item][weight]V[item-1][weight];}}}//Printing the matrixfor (int[] rows : V) {for (int col : rows) {System.out.format(%5d, col);}System.out.println();}return V[N][W];}}翻译自: https://www.javacodegeeks.com/2014/07/the-knapsack-problem.html背包问题九讲
