gpt-4-0314· OpenAI
WildChat-4.8M (AI2)
1. Write a java program to solve 0/1 knapsack problem using Branch and bound algorithm.…
- User
-
Write a java program to solve 0/1 knapsack problem using Branch and bound algorithm.
-
Write a java program that uses dynamic programming algorithm to solve the optimal binary search tree problem.
-
- Assistant
- 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); } }- 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); } }
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.