老刘聊肠道网 老刘聊肠道网
关注数: 28 粉丝数: 29 发帖数: 1,305 关注贴吧数: 22
【求助】java 0-1背包问题无法理解,求解 刚学算法设计与分析 ,现在在自学,看到个0-1背包问题,看了两遍,就像看天书,无法理解,还望大侠们指点迷津 书上的 思想如下:(m(i,j)还能理解,m(n,j)不知道是干什么有什么作用): ┌max(m(i+1,j),m(i+1,j-w[i])+v[i]) j>=w[i] ┌m(i,j)=│ │ └m(i+1,j) 0<=j<w[i] │ │ ┌v[n] j>w[n] //??? └m(n,j)=│ └0 0<=j<w[n] //??? 代码如下:(求帮忙解释下,注释下(每行)关键代码行的作用): public class Bag { //v:物品价值 w:物品质量 c:背包容量 //m(i,j):背包容量j,物品为i,i+1,i+2,...时的最优值 public void knapsack(int[] v, int[] w, int c, int[][] m) {//计算背包问题最优值 int n = v.length - 1; int jMax = Math.min(w[n] - 1, c);// for (int j = 0; j <= jMax; j++) m[n][j] = 0; for (int j = w[n]; j <= c; j++) m[n][j] = v[n]; for (int i = n - 1; i > 1; i--) { jMax = Math.min(w[i] - 1, c); for (int j = 0; j <= jMax; j++) m[i][j] = m[i + 1][j]; for (int j = w[i]; j <= c; j++) m[i][j] = Math.max(m[i + 1][j], m[i + 1][j - w[i]] + v[i]); } m[1][c] = m[2][c];// if (c >= w[1])// m[1][c] = Math.max(m[1][c], m[2][c - w[1] + v[1]]); } public void traceback(int[][] m, int[] w, int c, int[] x) {//构造背包问题最优解 int n = w.length - 1; for (int i = 1; i < n; i++) if (m[i][c] == m[i + 1][c]) x[i] = 0; else { x[i] = 1; c -= w[i]; } x[n] = (m[n][c] > 0) ? 1 : 0; } public static void main(String[] args) { Bag b=new Bag(); int v[]={1,3,5,7,9}; int w[]={2,4,6,8,10}; int c=20; //。。。。。。 } }
1 下一页