文件名称:Knapsack
- 所属分类：
- 控制台(字符窗口)编程
- 资源属性：
- [Java] [源码]
- 上传时间：
- 2013-11-28
- 文件大小：
- 2kb
- 下载次数：
- 0次
- 提 供 者：
- 相关连接：
- 无
- 下载说明：
- 别用迅雷下载，失败请重下，重下不扣分！
介绍说明－－下载内容均来自于网络，请自行研究使用
算法设计与分析中背包问题。
首先将最优解矩阵的第一行和第一列均赋值为0；然后从上至下、从左至右依次计算m[i][j]的值，如果第i个物品
的重量大于j的值，即第i个物品不放入背包中，则将m[i][j]赋值为m[i-1][j]，否则取第i个物品放入背包和不放入背
包所得价值的最大值；最后从后往前计算最优解向量的值，如果m[i][j]=m[i-1][j]，则将x[i]赋值为0，否则将x[i]
赋值为1，并将j减去第i个物品的重量。-The knapsack problem algorithm design and analysis. First, the optimal solution in the first row and first column of the matrix are assigned 0 then from top to bottom, computing m [i] [j] values from left to right, if the weight is greater than the i-th item j values, i.e., the i-th item is not put into the backpack, then m [i] [j] assigned to m [i-1] [j], otherwise, it is the i-th item is not put into the resultant bags and backpacks the maximum value finally calculate the optimal solution from the previous value of the vector, if m [i] [j] = m [i-1] [j], then the x [i] values 0, otherwise x [i] value of 1, the i-th and j minus the weight of the article.
首先将最优解矩阵的第一行和第一列均赋值为0；然后从上至下、从左至右依次计算m[i][j]的值，如果第i个物品
的重量大于j的值，即第i个物品不放入背包中，则将m[i][j]赋值为m[i-1][j]，否则取第i个物品放入背包和不放入背
包所得价值的最大值；最后从后往前计算最优解向量的值，如果m[i][j]=m[i-1][j]，则将x[i]赋值为0，否则将x[i]
赋值为1，并将j减去第i个物品的重量。-The knapsack problem algorithm design and analysis. First, the optimal solution in the first row and first column of the matrix are assigned 0 then from top to bottom, computing m [i] [j] values from left to right, if the weight is greater than the i-th item j values, i.e., the i-th item is not put into the backpack, then m [i] [j] assigned to m [i-1] [j], otherwise, it is the i-th item is not put into the resultant bags and backpacks the maximum value finally calculate the optimal solution from the previous value of the vector, if m [i] [j] = m [i-1] [j], then the x [i] values 0, otherwise x [i] value of 1, the i-th and j minus the weight of the article.
(系统自动生成,下载前可以参看下载内容)
下载文件列表
Knapsack.java