回溯算法装载问题java

装载问题是一种经典的组合优化问题，回溯算法是解决该问题的一种常用方法。下面是回溯算法解决装载问题的Java实现：

import java.util.Scanner;

public class LoadingProblem {
    private static int n; // 货物数量
    private static int c; // 载重量
    private static int[] w; // 货物重量数组
    private static int cw; // 当前载重量
    private static int bestw; // 最优载重量
    private static int r; // 剩余货物重量

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入货物数量：");
        n = scanner.nextInt();
        System.out.print("请输入载重量：");
        c = scanner.nextInt();
        w = new int[n];
        System.out.println("请输入每个货物的重量：");
        for (int i = 0; i < n; i++) {
            w[i] = scanner.nextInt();
        }
        scanner.close();

        cw = 0;
        bestw = 0;
        r = 0;
        for (int i = 0; i < n; i++) {
            r += w[i];
        }

        backTrack(0);

        System.out.println("最优载重量为：" + bestw);
    }

    /**
     * 回溯算法求解装载问题
     * 
     * @param i 当前考虑的货物编号
     */
    private static void backTrack(int i) {
        if (i >= n) { // 已经考虑完所有货物
            if (cw > bestw) {
                bestw = cw;
            }
            return;
        }
        r -= w[i]; // 选择当前货物
        if (cw + w[i] <= c) { // 可行性剪枝
            cw += w[i];
            backTrack(i + 1);
            cw -= w[i];
        }
        if (cw + r > bestw) { // 限界剪枝
            backTrack(i + 1);
        }
        r += w[i]; // 不选择当前货物
    }
}