背包问题

网站地址

http://www.karaffeltut.com/NEWKaraffeltutCom/Knapsack/knapsack.html

简单遍历代码

public static int N = 5;
public static int W = 20;
public int[][] value = new int[N+1][W+1];

public int[] w = {0, 3, 2, 4, 9, 5};
public int[] v = {0, 4, 3, 5, 10, 8};


public static void main(String[] args) {
    Main main = new Main();
    main.Knapsack();
    System.out.println(main.value[5][20]);
}


public void Knapsack() {
    for (int i = 1; i <=N; i++) {
        for (int j = 1; j <= W; j++) {
            System.out.println("当前第" + i + "的重量为:" + w[i] + "   当前总体积j:" + j);
            if (w[i] > j) {
                value[i][j] = value[i - 1][j];
                System.out.println("第" + i + "," + j + ":   " + value[i][j]);
            } else {
                int value1 = value[i - 1][j];
                System.out.println(value1);
                int value2 = value[i - 1][j - w[i]] + v[i];
                System.out.println(value2);
                value[i][j] = value1 > value2 ? value1 : value2;
                System.out.println("第" + i + "," + j + ":   " + value[i][j]);
            }
        }
    }
}