编辑代码

class Main {
	  static final int N = 5;  //5件物品
    static final int W = 10; //限重10
    static int []w = {6,5,4,2,1}; //每件物品的重量
    static int []v = {5,3,5,3,2}; //每件物品的价值
    static int curValue; //记录当前的价值
    static int curWeight;
    static int bestValue;
    static int []x = new int[5];
    static int []bestX = new int[5];
    public static void main(String[] args) {
        backtracking(0);

        System.out.println("最大的价值: " + bestValue);
        System.out.print("选择的物品: ");
        for (int i = 0; i < N; i++) {
            System.out.print(bestX[i]+" ");
        }
    }

    public static void backtracking(int k) {
        if (k > N-1) {  //递归基，结算并退出此重调用
            if (bestValue < curValue) {
                bestValue = curValue;
                for (int i = 0; i < N; i++) {
                    bestX[i] = x[i];
                }
            }
        }
        else {
            for (int i = 0; i <= 1; i++) { //循环01
                x[k] = i;
                if (i == 0) {
                    backtracking(k+1);
                }
                else {
                    if (curWeight + w[k] < W) {
                        curWeight += w[k];
                        curValue += v[k];
                        backtracking(k+1);
                        curWeight -= w[k]; //回溯后还原原先情况
                        curValue -= v[k];
                    }
                }
            }
        }
    }
}