回溯算法解决0-1背包问题升级版–计算价值最高

需求：对于一组不同重量、不同价值、不可分割的物品，我们需要选择一些装入背包，计算满足背包重量的前提下，装入背包的物品的最大价值是多少呢？
之所以叫0-1背包问题，就是因为物品不可分割。

相比前面的0-1背包问题，这里的升级版问题引入了物品价值，考虑的维度多了一个。

我们先回顾一下之前讲过的回溯算法的逻辑：
回溯算法的实现逻辑是穷举所有可能，找出最佳结果，回溯算法一般是使用递归来编写代码，既然用到递归，就需要些递归公式。
用回溯算法实现0-1背包，主要实现思路就是穷举每个物品，每个物品都有两种可能，一种是放入背包，一种是不放入背包。
对于 n 个物品来说，总的装法就有 2^n 种，去掉总重量超过 Wkg 的，从剩下的装法中选择总重量最接近 Wkg 的。

我们来看代码:

/**
 * 背包0-1问题  回溯算法
 *
 */
public class BeiBao_HuiSu2 {

    // 物品重量
    private static final int[] weight = {2,2,4,6,3};

    // 物品的价值
    private static int[] value = {5,2,8,12,6};

    // 物品个数
    private static final int n = 5;

    // 背包承受的最大重量
    private static final int w = 9;

    //private static int maxWeight = Integer.MIN_VALUE;
    private static int maxValue = Integer.MIN_VALUE;

    public static void main(String[] args) {
        long t1 = System.currentTimeMillis();
        BeiBao_HuiSu2.getMaxWeight(0,0, 0);
        long t2 = System.currentTimeMillis();
        System.out.println(maxValue+":计算时间:"+(t2-t1));
        maxValue = Integer.MIN_VALUE;
        long t3 = System.currentTimeMillis();
        BeiBao_HuiSu2.getMaxWeight2(0,0, 0);
        long t4 = System.currentTimeMillis();
        System.out.println(maxValue+":计算时间:"+(t4-t3));
    }

    public static void getMaxWeight(int i, int rw, int rv) {
        //表示物品重量已经达到最大值或没有达到最大值但是所有物品已经都计算过了
        if(rw == w || i == n ) {
            if(rw > maxValue) {
                maxValue = rv;
            }
            return;
        }

        //第i个不放入背包
        getMaxWeight(i+1, rw, rv);

        if(weight[i]+rw <= w) {
            //第i个放入背包
            getMaxWeight(i+1, weight[i]+rw, rv+value[i]);
        }

    }

    public static boolean[][] record = new boolean[5][10];

    /**
     * 优化性能，去掉重复计算
     * @param i
     * @param rw
     */
    public static void getMaxWeight2(int i, int rw, int rv) {
        //表示物品重量已经达到最大值或没有达到最大值但是所有物品已经都计算过了
        if(rw == w || i == n ) {
            if(rw > maxValue) {
                maxValue = rv;
            }
            return;
        }

        //添加计算记录、检查是否已计算
        if(record[i][rw]) {
            return;
        }
        record[i][rw] = true;

        //第i个不放入背包
        getMaxWeight2(i+1, rw, rv);

        if(weight[i]+rw <= w) {
            //第i个放入背包
            getMaxWeight2(i+1, weight[i]+rw, rv+value[i]);
        }

    }

}

/* 输出
18
18
 */

我们在简单0-1背包问题中使用了一个标记数组来减少重复计算，那么升级的背包问题能不能也用标记来避免重复计算呢？
答案是否定的，因为重量相同的物品价值可能不一样，比如这种情况：

// 物品重量
private static final int[] weight = {2,2,2,2,2};

// 物品的价值
private static int[] value = {5,15,25,35,45};

这种情况就不能用二维数组去减少重复物品的计算，你可能会说，我可以用一个三维数组来避免重复计算，理论上是可以的，但是有一个问题，如果不知道价值维度的上限，那么这个数组就没法定义。
所以如果遇到较大计算量时，回溯算法就不适合了，此时可以选择动态规划。