Skip to content
TheChatArchiveThe Chat Archive
gpt-4-0314· OpenAIAi2 WildChat-4.8M (AI2)

1. Write a java program to solve 0/1 knapsack problem using Branch and bound algorithm.…

  1. User
    1. Write a java program to solve 0/1 knapsack problem using Branch and bound algorithm.

    2. Write a java program that uses dynamic programming algorithm to solve the optimal binary search tree problem.

  2. Assistant
    1. Java program to solve 0/1 knapsack problem using a branch and bound algorithm:
    import java.util.*;
    
    class Item {
        int weight, value, index;
        Item(int index, int weight, int value) {
            this.index = index;
            this.weight = weight;
            this.value = value;
        }
    }
    
    class Node {
        int level, profit, bound;
        int weight;
        boolean[] path;
        
        Node(int n) {
            this.path = new boolean[n+1];
        }
    }
    
    public class KnapsackBranchAndBound {
        
        private static int[] values;
        private static int[] weights;
        private static int n;
        private static int capacity;
    
        private static int bound(Node u) {
            int j, k;
            int totweight;
            int res;
            
            if (u.weight >= capacity) {
                return 0;
            }
            
            j = u.level + 1;
            totweight = u.weight;
            res = u.profit;
            
            while (j < n && totweight + weights[j] <= capacity) {
                totweight += weights[j];
                res += values[j];
                j++;
            }
            
            k = j;
            
            if (j < n) {
                res += (capacity - totweight) * values[k] / weights[k];
            }
            
            return res;
        }
        
        public static int knapSack() {
            Arrays.sort(weights);
    
            PriorityQueue<Node> pq = new PriorityQueue<>(1, Comparator.comparingInt(n -> -n.bound));
    
            Node u = new Node(n);
            Node v = new Node(n);
            
            v.level = -1;
            v.profit = v.weight = 0;
    
            v.bound = bound(v);
            pq.offer(v);
            int maxProfit = 0;
            
            while (!pq.isEmpty()) {
                v = pq.poll();
    
                if (v.bound > maxProfit) {
                    u.level = v.level + 1;
                    u.weight = v.weight + weights[u.level];
                    u.profit = v.profit + values[u.level];
                    u.path[u.level] = true;
    
                    if (u.weight <= capacity && u.profit > maxProfit) {
                        maxProfit = u.profit;
                    }
                    
                    u.bound = bound(u);
    
                    if (u.bound > maxProfit) {
                        pq.offer(u);
                    }
                    
                    u = new Node(n);
                    System.arraycopy(v.path, 0, u.path, 0, n + 1);
                    u.level = v.level + 1;
                    u.weight = v.weight;
                    u.profit = v.profit;
                    u.bound = bound(u);
    
                    if (u.bound > maxProfit) {
                        pq.offer(u);
                    }
                }
            }
            
            return maxProfit;
        }
        
        public static void main(String[] args) {
            values = new int[] {60, 100, 120};
            weights = new int[] {10, 20, 30};
            n = values.length;
            capacity = 50;
            
            int max_profit = knapSack();
            System.out.println("Max Profit using Branch and Bound: " + max_profit);
        }
    }
    
    1. Java program that uses a dynamic programming algorithm to solve the optimal binary search tree problem:
    public class OptimalBST {
        public static void optimalSearchTree(int[] keys, int[] freq, int n) {
            int[][] cost = new int[n + 1][n + 1];
    
            for (int i = 0; i < n; i++) {
                cost[i][i] = freq[i];
            }
    
            for (int len = 2; len <= n; len++) {
                for (int i = 0; i <= n - len + 1; i++) {
                    int j = i + len - 1;
                    cost[i][j] = Integer.MAX_VALUE;
    
                    for (int r = i; r <= j; r++) {
                        int c = ((r > i) ? cost[i][r - 1] : 0) + ((r < j) ? cost[r + 1][j] : 0) + sum(freq, i, j);
                        if (c < cost[i][j]) {
                            cost[i][j] = c;
                        }
                    }
                }
            }
    
            System.out.println("Cost of Optimal BST: " + cost[0][n - 1]);
        }
    
        public static int sum(int[] arr, int start, int end) {
            int sum = 0;
            for (int i = start; i <= end; i++) {
                sum += arr[i];
            }
            return sum;
        }
    
        public static void main(String[] args) {
            int[] keys = {10, 12, 20};
            int[] freq = {34, 8, 50};
            int n = keys.length;
            optimalSearchTree(keys, freq, n);
        }
    }
    

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.