学步园

关于01背包问题，可以使用回溯法解决。另外，这个方法还可以衍生到其他的一些问题的解决上。
比如：
1.有两艘船，载重量分别是w1，和w2，现在有一批货，如何装载，是的两艘船能够装载尽量多的货物。
    这个题目就可以用01背包的方法解决。即先计算一艘船的背包问题，然后用剩下的货物计算另一艘船的背包问题。
2.给定一个正整数的集合和一个值（c），是否存在集合的一个子集，是的子集里元素的和是否等于c。
    与01背包的解法类似。   
3.设某一机器有n个部件组成,每一种部件都可以从m个不同的的供应商出购得,各种供应商提供的相同部件的价格和重量都不同,是找出总价格不超过价格上限的最小机器重量.
    这个问题同样可以用01背包解决,只是在回溯函数里,需要加入一个循环,计算每个供应商购得零件后的价格和重量.

/**
 * 01背包问题
 * 使用回溯算法实现
 * @author ztl
 *
 */
public class Knapsack {
    private int[] weight;
    private int maxWeight;
    private int currentWeight;
    private int bestWeight;
    private int height;
    private int[] state;
    private int[] currentState;
    public Knapsack(int mw,int[] weightSet){
        this.maxWeight = mw;
        this.weight = weightSet;
        this.currentWeight = 0;
        this.bestWeight = 0;
        this.height = weightSet.length - 1;//要减一，是因为第一个节点的height是0
        state = new int[weightSet.length];
        currentState = new int[weightSet.length];
        backtrace(0);
        printResult();
    }
    
    public void backtrace(int i){
        if (i > height){//到达了叶节点
            if (currentWeight > bestWeight){
                bestWeight = currentWeight;
                for (int j=0;j<state.length;j++){
                    state[j] = currentState[j];
                }
            }
            return;
        }
        
        if (currentWeight + weight[i] <= maxWeight){//检查右子树
            currentWeight += weight[i];
            currentState[i] = 1;
            backtrace(i+1);
            currentWeight -= weight[i];
            currentState[i] = 0;
        }
        backtrace(i+1);//检查左子树
    }
    
    public void printResult(){
        System.out.println("result is "+bestWeight);
        for (int i=0;i<state.length;i++){
            System.out.print(state[i] + " ");
        }
        System.out.println();
        
        
    }
    
    public static void main(String args[]){
        int[] weight = {2,5,4,7,16,11,13};
        new Knapsack(10,weight);
    }
}