回溯算法解决0-1背包问题

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

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

我们来看代码:

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

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

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

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

    private static int maxWeight = Integer.MIN_VALUE;

    public static void main(String[] args) {
        BeiBao_HuiSu.getMaxWeight(0,0);
        System.out.println(maxWeight);
    }

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

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

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

    }

}
/* 输出
9
*/

上面代码的写法其实有好多重复计算，可以增加一个计算标记来降低计算量。

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

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

	//添加计算记录、检查是否已计算
	if(record[i][rw]) return;
	record[i][rw] = true;
	
	//第i个不放入背包
	getMaxWeight2(i+1, rw);

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

}