Practical No 4
4. Write a program to solve a 0-1 Knapsack problem using dynamic programming or branch
and bound strategy.Code:
1. Dynamic Programming Approach
Code:
public class KnapsackDP {
// Function to solve 0-1 Knapsack problem using Dynamic Programming
public static int knapSack(int capacity, int[] weights, int[] values, int n) {
int[][] dp = new int[n + 1][capacity + 1]; // Create a DP table
// Fill the DP table
for (int i = 1; i <= n; i++) {
for (int w = 1; w <= capacity; w++) {
if (weights[i - 1] <= w) {
// If the item can be included
dp[i][w] = Math.max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]]);
} else {
// If the item cannot be included
dp[i][w] = dp[i - 1][w];
return dp[n][capacity]; // Return the maximum value that can be achieved
public static void main(String[] args) {
int[] values = {60, 100, 120}; // Values of items
int[] weights = {10, 20, 30}; // Weights of items
int capacity = 50; // Capacity of knapsack
int n = values.length; // Number of items
int maxValue = knapSack(capacity, weights, values, n);
System.out.println("Maximum value in the knapsack = " + maxValue);
Explanation of Dynamic Programming Code:
1. Initialization:
o A 2D array dp is created, where dp[i][w] represents the maximum value achievable with
the first i items and maximum weight w.
2. Filling the DP Table:
o The table is filled iteratively. For each item, we check if it can be included in the knapsack
(if its weight is less than or equal to w):
▪ If it can be included, we take the maximum of either including it (adding its value
and the best we can do with the remaining weight) or not including it.
▪ If it cannot be included, we simply carry forward the maximum value from the
previous item.
3. Result:
o The maximum value for the entire capacity is found at dp[n][capacity].
2. Branch and Bound Approach
The Branch and Bound method is more complex but can be more efficient in certain scenarios. It
systematically explores branches of the solution space by making choices and pruning branches that
cannot yield better results than already found solutions.
Code:
import java.util.Arrays;
import java.util.Comparator;
class Item {
int value;
int weight;
public Item(int value, int weight) {
this.value = value;
this.weight = weight;
class Node {
int level; // Level of the node in the decision tree
int profit; // Profit at the node
int bound; // Upper bound of profit
int weight; // Weight at the node
public Node(int level, int profit, int weight, int bound) {
this.level = level;
this.profit = profit;
this.weight = weight;
this.bound = bound;
public class KnapsackBranchBound {
// Function to calculate upper bound
public static int bound(Node node, int n, int capacity, Item[] items) {
if (node.weight >= capacity) {
return 0; // If weight exceeds capacity, return 0
}
int profitBound = node.profit; // Start with the current profit
int j = node.level + 1; // Start from the next item
int totalWeight = node.weight; // Start from the current weight
// Add items to the profitBound
while (j < n && totalWeight + items[j].weight <= capacity) {
totalWeight += items[j].weight; // Add weight
profitBound += items[j].value; // Add profit
j++;
// If there are still items left, add a fraction of the next item
if (j < n) {
profitBound += (capacity - totalWeight) * items[j].value / items[j].weight;
return profitBound; // Return the bound
// Function to solve the 0-1 Knapsack problem using Branch and Bound
public static int knapsack(int capacity, Item[] items, int n) {
// Sort items by value-to-weight ratio
Arrays.sort(items, new Comparator<Item>() {
@Override
public int compare(Item i1, Item i2) {
double r1 = (double) i1.value / i1.weight;
double r2 = (double) i2.value / i2.weight;
return Double.compare(r2, r1); // Sort in descending order
});
Node u = new Node(-1, 0, 0, 0); // Start with an empty node
Node v;
int maxProfit = 0; // Max profit found so far
// Create a priority queue (or similar structure) for nodes
java.util.PriorityQueue<Node> pq = new java.util.PriorityQueue<>(Comparator.comparingInt(node -
> -node.bound));
u.bound = bound(u, n, capacity, items);
pq.offer(u); // Add the initial node to the queue
while (!pq.isEmpty()) {
u = pq.poll(); // Get the node with the highest bound
// If we reached the last level
if (u.level == n - 1) {
continue;
// Explore the next level
v = new Node(u.level + 1, u.profit + items[u.level + 1].value, u.weight + items[u.level + 1].weight,
0);
if (v.weight <= capacity && v.profit > maxProfit) {
maxProfit = v.profit; // Update max profit
}
// Calculate the bound for the new node
v.bound = bound(v, n, capacity, items);
if (v.bound > maxProfit) {
pq.offer(v); // Add to the queue if the bound is promising
// Explore the node where the next item is not included
v = new Node(u.level + 1, u.profit, u.weight, 0);
v.bound = bound(v, n, capacity, items);
if (v.bound > maxProfit) {
pq.offer(v); // Add to the queue if the bound is promising
return maxProfit; // Return the maximum profit found
public static void main(String[] args) {
Item[] items = {
new Item(60, 10),
new Item(100, 20),
new Item(120, 30)
};
int capacity = 50; // Capacity of the knapsack
int n = items.length; // Number of items
int maxProfit = knapsack(capacity, items, n);
System.out.println("Maximum profit in the knapsack = " + maxProfit);
}
Explanation of Branch and Bound Code:
1. Item Class:
o Similar to the previous implementation, we create an Item class to hold the value and
weight of each item.
2. Node Class:
o The Node class represents a node in the decision tree, containing information about the
level, profit, weight, and upper bound.
3. Bound Calculation:
o The bound method calculates the upper bound of profit for a given node, taking into
account the current profit and the potential profit from the remaining items.
4. Main Knapsack Function:
o The knapsack function begins by sorting the items based on their value-to-weight ratio
in descending order.
o It uses a priority queue to manage nodes based on their bound.
o It iteratively explores nodes, adding either the next item or skipping it, while updating
the maximum profit found.
5. Main Method:
o The main method initializes the items and capacity, then calls the knapsack function to
calculate and print the maximum profit.
