博客

先前用C语言很容易实现了一个回溯算法，但转到Java后由于面向对象的原因，一时不知道如何处理变量。今天学习了static和final关键字，正好做一个练习。


static: 定义一个类变量，使当前变量可以此类中的任意方法访问



final: 定义一个常量

package Foundation;

/**
 * @PackageName: Foundation
 * @ClassName: Bag
 * @Description: 回溯法实现01背包问题及final, static关键字的使用
 * @Author: codeslogan
 * @Date: 2021-09-02 16:00
 */
public class Bag {

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

        System.out.println("最大利润为: " + bestValue);
        for (int i = 0; i < N; i++) {
            System.out.println(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];
                    }
                }
            }
        }
    }
}