回溯法 普通01背包问题

普通01背包问题与01背包问题的差别在于，

必须要求放进背包的物品总重量，恰好等于背包容量，

而不是求最优

public class Bags01 {

    static int[] m=new int[]{,,,,};//物品重量
    static int[] now=new int[]{,,,,};//记录是否取某个物品
    static int sum=;//解决总方案数

    public static void f(int weight,int num){
       // System.out.println("weight :"+weight+"  num :"+num);

        if(weight<||(weight>&&num<=)) return;
        if(weight==){
            sum++;
            System.out.println("sum ="+sum+"\nresult:");
            for(int i : now)
            System.out.print(i+"  ");
            System.out.println();
            return;
        }
        //do something
        now[num-]=;
        f(weight-m[num-],num-);

        //undo something（撤销此步操作，直接进入下一步）
        now[num-]=;
        f(weight,num-);
    }

    public static void main(String[] args){
        int n=,weight=;//背包容量
        f(weight,n);
    }

}
//output
/*
sum =1
result:
0  1  0  0  1  
sum =2
result:
0  0  1  1  0 
*/