最优装载问题回溯法java

最优装载问题是指在满足总重量不超过给定限制的情况下，尽可能地装载货物，使得货物的价值最大化。这是一个NP完全问题，可以使用回溯法求解。

以下是一个基于回溯法的Java实现：

public class Knapsack {
    private int[] weights; // 货物重量数组
    private int[] values; // 货物价值数组
    private int capacity; // 背包容量
    private int[] solution; // 最优解

    public Knapsack(int[] weights, int[] values, int capacity) {
        this.weights = weights;
        this.values = values;
        this.capacity = capacity;
        this.solution = new int[weights.length];
    }

    public void backtrack(int[] path, int pathLen, int weight, int value) {
        if (weight <= capacity && value > solutionValue()) {
            // 如果当前方案比已知最优解更优，更新最优解
            System.arraycopy(path, 0, solution, 0, pathLen);
        }

        for (int i = pathLen; i < weights.length; i++) {
            if (weight + weights[i] <= capacity) {
                path[pathLen] = i;
                backtrack(path, pathLen + 1, weight + weights[i], value + values[i]);
            }
        }
    }

    public int[] solve() {
        int[] path = new int[weights.length];
        backtrack(path, 0, 0, 0);
        return solution;
    }

    public int solutionValue() {
        int sum = 0;
        for (int i = 0; i < solution.length; i++) {
            sum += values[solution[i]];
        }
        return sum;
    }
}

使用示例：

int[] weights = {2, 3, 4, 5};
int[] values = {3, 4, 5, 6};
int capacity = 8;
Knapsack knapsack = new Knapsack(weights, values, capacity);
int[] solution = knapsack.solve();
System.out.println(Arrays.toString(solution));

输出结果为：

[0, 1, 3]

表示选择了第1、2、4个货物，总重量为2+3+5=10，总价值为3+4+6=13，是最优解。