package knapsack;

import java.util.*;



class Node {
    int level;    // nodes level in the tree
    int weight;   // nodes weight
    int profit;   // nodes profit

    public Node() {  // set all default values to 0
        level = 0;
        weight = 0;
        profit = 0;
    }
    public Node(int level, int weight, int profit) { // method to call Node class
        this.level = level;
        this.weight = weight;
        this.profit = profit;
    }

}

public class knapsack {
    public static int[] w = {2, 5, 10, 5};  // array of weights
    public static int[] p = {40, 30, 50, 10};  // array of profits
    public static int W = 16;    // sums of weights cannot exceed W
    public static int n = 4;   // number of items

    public static int knapsack2(int n, int[] p, int[] w, int W) {
        Queue<Node> Q = new LinkedList<>();     //
        Node v = new Node();  // declare two node objects v and u
        Node u = new Node();
        int maxProfit = 0;
        Q.add(v); // enqueue Node v so that loop will run
        v.level = -1;
        while(!Q.isEmpty()) {
            v = Q.remove();  // dequeue node v
            u = new Node();
            if (v.level == -1)
                u.level = 0;
            else
                u.level = v.level + 1;
            u.weight = v.weight + w[u.level];
            u.profit = v.profit + p[u.level];
            if(u.weight <= W && u.profit > maxProfit)                                         // next item
                maxProfit = u.profit;
            if(bound(u, n, p, w, W) > maxProfit)
                Q.add(u);
            u = new Node();
            u.level = v.level + 1;
            u.weight = v.weight;                // Set u to the child of v that does not include the next item
            u.profit = v.profit;
            if(bound(u, n, p, w, W) > maxProfit)
                Q.add(u);
        }
        return maxProfit;
    }

    public static double bound(Node u, int n, int[] p, int[] w, int W) {
        if (u.weight >= W)
            return 0;
        int j = u.level + 1, totweight = u.weight;
        double result = u.profit;
        while(j <= n && (totweight + w[j]) <= W) {
            totweight += w[j];          // grab as many items as possible
            result += p[j];
            j++;
        }
        int k = j;
        if (k <= n)                                 // grab function of kth item
            result += (W - totweight) * ((double)p[k]/w[k]);
        return result;
    }

    public static void main(String[] args) {

        System.out.println("Max Profit: " + knapsack2(n-1, p, w, W));

    }
}