0-1背包问题的回溯算法Java实现

可以参考以下代码：

public class Knapsack {

public static int knapSack(int W, int wt[], int val[], int n) {

if (n == 0 || W == 0) {
return 0;
}

if (wt[n - 1] > W) {
return knapSack(W, wt, val, n - 1);
} else {
return Math.max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), knapSack(W, wt, val, n - 1));
}
}

public static void main(String args[]) {
int val[] = new int[]{60, 100, 120};
int wt[] = new int[]{10, 20, 30};
int W = 50;
int n = val.length;
System.out.println(knapSack(W, wt, val, n));
}
}

笑话：为什么程序员总是说“它应该可以运行”？因为他们总是忘记了边界条件！

相关问题

0-1背包问题的回溯算法Java

以下是0-1背包问题的回溯算法Java代码实现：

public class KnapsackBacktracking {

    private int maxWeight = 0;
    private boolean[] bestSolution;
    private int[] weights;
    private int[] values;
    private int capacity;

    public int knapsack(int[] weights, int[] values, int capacity) {
        this.weights = weights;
        this.values = values;
        this.capacity = capacity;
        bestSolution = new boolean[weights.length];
        backtracking(0, 0, 0, new boolean[weights.length]);
        return maxWeight;
    }

    private void backtracking(int i, int weight, int value, boolean[] solution) {
        if (i == weights.length || weight == capacity) {
            if (value > maxWeight) {
                maxWeight = value;
                System.arraycopy(solution, 0, bestSolution, 0, solution.length);
            }
            return;
        }
        if (weight + weights[i] <= capacity) {
            solution[i] = true;
            backtracking(i + 1, weight + weights[i], value + values[i], solution);
        }
        solution[i] = false;
        backtracking(i + 1, weight, value, solution);
    }

    public boolean[] getBestSolution() {
        return bestSolution;
    }
}

其中，`knapsack()`方法接收物品重量数组`weights`、价值数组`values`和背包容量`capacity`，并返回最大价值。`backtracking()`方法是递归函数，用来搜索所有可能的解，并更新最优解。`maxWeight`和`bestSolution`分别用来保存最大价值和最优解。在递归过程中，如果当前重量或价值已经达到最大值，则结束递归。否则，对于每个物品，我们可以选择将其放入背包或不放入，分别递归求解。最后，通过`getBestSolution()`方法来获取最优解。

0-1背包问题的回溯算法java

可以参考以下代码实现：

public class KnapsackProblem {
    public static int maxValue = 0;
    public static int[] weights = {2, 2, 4, 6, 3};
    public static int[] values = {3, 4, 8, 9, 6};
    public static int capacity = 9;

    public static void main(String[] args) {
        int n = weights.length;
        backtrack(0, 0, 0, n);
        System.out.println("The maximum value is " + maxValue);
    }

    public static void backtrack(int i, int weight, int value, int n) {
        if (i == n) {
            if (weight <= capacity && value > maxValue) {
                maxValue = value;
            }
            return;
        }
        backtrack(i + 1, weight, value, n);
        if (weight + weights[i] <= capacity) {
            backtrack(i + 1, weight + weights[i], value + values[i], n);
        }
    }
}

当然，这只是回溯算法的一种实现，还有其他的实现方式，具体选择哪种实现方式需要根据具体情况来决定。