java0-1背包回溯法代码_0-1背包问题回溯法

好的，这是一个背包问题的回溯算法（Java实现）：

public class Knapsack {
    private static int maxW = Integer.MIN_VALUE; //果放到maxW中
    private static int[] weight = {2, 2, 4, 6, 3};  // 物品重量
    private static int n = 5; // 物品个数
    private static int[] value = {3, 4, 8, 9, 6}; // 物品价值
    private static int w = 9; // 背包承受的最大重量

    public static void main(String[] args) {
        f(0, 0);
        System.out.println(maxW);
    }

    /**
     * @param i     考察到第i个物品
     * @param cw    当前已经装进去的物品的重量和
     */
    private static void f(int i, int cw) {
        if (cw == w || i == n) { // cw==w表示装满了;i==n表示物品都考察完了
            if (cw > maxW) maxW = cw;
            return;
        }
        f(i + 1, cw); // 选择不装第i个物品
        if (cw + weight[i] <= w) {
            f(i + 1, cw + weight[i]); // 选择装第i个物品
        }
    }
}

其中，weight和value数组分别表示物品的重量和价值，n表示物品个数，w表示背包承受的最大重量。在f函数中，i表示考察到第i个物品，cw表示当前背包中已经装入的物品的重量和。首先尝试不装第i个物品，然后再尝试装第i个物品，如果装入后总重量不超过背包承受的最大重量，则继续往下考察。最后，返回装入物品的总重量maxW。