import java.util.Arrays;

public class BranchBound_zerooneknapsack {
    static boolean isDebugMode = false;
    static int curBestSolution = -1;

    public static void main(String[] args)
    {
        double capacity_weight = 10;
        Integer[] weight = new Integer[]{2, 3, 2, 5, 3};
        Integer[] val = new Integer[]{40, 50, 100, 95, 30};

//        double capacity_weight = 50;
//        Integer[] weight = new Integer[]{10, 20, 30};
//        Integer[] val = new Integer[]{60, 100, 120};


        System.out.println("v: ");
        printArray(val);
        System.out.println("w: ");
        printArray(weight);

        Integer finalVal = backtracking_BranchAndBound(capacity_weight, val, weight);

        System.out.println("result: ");
        System.out.println(finalVal);
    }

    private static Integer backtracking_BranchAndBound(double capacity_weight, Integer[] vals, Integer[] weights) {
        Integer curWeight = 0;
        Integer curVal = 0;
        Integer curIndex = 0;
        int finalVal = goDownDFS(capacity_weight, vals, weights, curWeight, curVal, curIndex);
        return finalVal;
    }

    private static Integer goDownDFS(double capacity_weight, Integer[] vals, Integer[] weights, Integer curWeight, Integer curVal, Integer curIndex) {
        // ending point
        if ( curWeight > capacity_weight) { // backtracking here
            return -1; // 爆了，所以當作最小價值
        }
        if (curIndex >= vals.length) {
            return curVal;
        }

        // branch and bound
        int greatestValForCurrentNode = getGreatestValForCurrentNode(curVal, vals, curIndex);
        if (greatestValForCurrentNode <= curBestSolution) return -1;

        // if take
        int ifTakeWeight = curWeight + weights[curIndex];
        int ifTakeVal = curVal + vals[curIndex];
        int ifTakeCurrVal = goDownDFS(capacity_weight, vals, weights, ifTakeWeight, ifTakeVal, curIndex+1);

        // if not take
        int ifNotTakeWeight = curWeight;
        int ifNotTakeVal = curVal;
        int ifNotTakeCUrrVal = goDownDFS(capacity_weight, vals, weights, ifNotTakeWeight, ifNotTakeVal, curIndex+1);

        int max = Math.max(ifTakeCurrVal, ifNotTakeCUrrVal);
        if (max > curBestSolution) curBestSolution = max;
        return max;

    }

    private static Integer getGreatestValForCurrentNode(Integer curVal, Integer[] vals, Integer curIndex) {
        int result = curVal;
        for (int i = curIndex; i < vals.length; i++) {
            result += vals[i];
        }
        return result;
    }


    ///// Util Only below /////

    public static int[][] generateDeepCopy2dAry(int[][] original) {
        if (original == null) {
            return null;
        }

        final int[][] result = new int[original.length][];
        for (int i = 0; i < original.length; i++) {
            result[i] = Arrays.copyOf(original[i], original[i].length);
            // For Java versions prior to Java 6 use the next:
            // System.arraycopy(original[i], 0, result[i], 0, original[i].length);
        }
        return result;
    }

    private static void printArray(Object[] ary){
        for (int i = 0; i < ary.length; i++) {
            System.out.printf("%4d" , ary[i]);
        }
        System.out.println();
    }
    private static void print2DArray(int[][] ary){
        for (int i = 0; i < ary.length; i++) {
            for (int j = 0; j < ary[i].length; j++) {
                System.out.printf("%4d" , ary[i][j]);
            }
            System.out.println();
        }
    }
}