Rod Cutting Problem

Problem Statement: Given a rod of length n inches and an array of prices that contains prices of all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces. For example, if length of the rod is 8 and the values of different pieces are given as following, then the maximum obtainable value is 22 (by cutting in two pieces of lengths 2 and 6).

GFG Link: https://www.geeksforgeeks.org/cutting-a-rod-dp-13/

Practice Link: https://practice.geeksforgeeks.org/problems/rod-cutting/0

Solution:

01 Knapsack Problem Print All Solutions using Dynamic Programming [01 Knapsack][Dynamic Programming][All Solutions][Java]

This program uses Dynamic Programming to solve the 01 Knapsack problem and prints all the possible solutions to a given problem. All solution printer is a separate recursive function. Also displays a nicely formatted table constructed during evaluation of the problem.

Code:

import java.util.Arrays;
import java.util.Scanner;

public class Knapsack01DynamicAllSolutions {

    int[][] table;
    int[] weight;
    int[] benefit;
    int capacityKnapsack;
    int nItems;

    Scanner scan = new Scanner(System.in);

    int B(int items, int maxCapacity) {

        if (maxCapacity < 0 || items < 0) {
            return -2;
        }

        if (table[items][maxCapacity] != -1) {
            return table[items][maxCapacity];
        }

        int arg1 = B(items - 1, maxCapacity);
        int arg2 = B(items - 1, (maxCapacity - weight[items - 1]));
        if (arg2 == -2) {
            arg2 = 0;
        } else {
            arg2 += benefit[items - 1];
        }
        table[items][maxCapacity] = Math.max(arg1, arg2);
        return table[items][maxCapacity];
    }

    void printAllItems(int row, int col) {
        if (row == 0) { return; }
        
        while (table[row][col] == table[row - 1][col]) {
            int number = col - weight[row - 1];
            int ben = benefit[row - 1];

            if(number==0 && benefit[row-1] == table[row-1][col]){System.out.print("[ "+row+" ] ");}
            if (number <= 0) {
                ben = 0;
                number = 0;
            }
            if (table[row][col] == table[row - 1][number] + ben) {
                //include this item  
                System.out.print("[ ");
                System.out.print(row + " ");
                printAllItems(row - 1, col - weight[row - 1]);
                System.out.print("] ");
            } 
            row--;
            if (row == 1) {
                break;
            }
        }

        if (table[row][col] != table[row - 1][col]) {
            System.out.print(row + " "); 

            if (col - weight[row - 1] > 0) {
                printAllItems(row - 1, col - weight[row - 1]); 
                
            }
        }
    }  

    void input() {
        System.out.println("Enter the number of items: ");
        nItems = scan.nextInt();

        System.out.println("Enter the (weight and benefit)s of the n items: ");

        weight = new int[nItems];
        benefit = new int[nItems];

        for (int i = 0; i < nItems; ++i) {
            weight[i] = scan.nextInt();
            benefit[i] = scan.nextInt();
        }

        System.out.println("Max capacity of the knapsack: ");
        capacityKnapsack = scan.nextInt();
        table = new int[nItems + 1][capacityKnapsack + 1];

        for (int i = 1; i < nItems + 1; ++i) {
            Arrays.fill(table[i], -1);
        }
        for (int i = 0; i < nItems + 1; ++i) {
            table[i][0] = 0;
        }
    }

    void printTable() {
        System.out.println();
        System.out.print("   ");
        int count = 0;
        for (int i = 0; i < capacityKnapsack + 1; ++i) {
            System.out.printf("%3d ", i);
        }
        System.out.println("\n");
        for (int i = 0; i < nItems + 1; ++i) {
            System.out.printf("%-3d", count);
            for (int j = 0; j < capacityKnapsack + 1; ++j) {
                System.out.printf("%1$3d ", table[i][j]);
            }
            count++;
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Knapsack01DynamicAllSolutions kd = new Knapsack01DynamicAllSolutions();
        kd.input();
        kd.B(kd.nItems, kd.capacityKnapsack);
        kd.printTable(); 
        kd.printAllItems(kd.nItems, kd.capacityKnapsack);
    }
}

Output:

Enter the number of items:
6
Enter the (weight and benefit)s of the n items:
2 3
2 1
1 3
3 4
5 3
2 1
Max capacity of the knapsack:
8

     0   1   2   3   4   5   6   7   8

0    0   0   0   0   0   0   0   0   0
1    0   0   3   3   3   3   3   3   3
2    0   0   3   3   4   4   4   4   4
3    0   3  -1   6  -1   7   7  -1   7
4    0   3  -1   6  -1  -1  10  -1  11
5    0  -1  -1  -1  -1  -1  10  -1  11
6    0  -1  -1  -1  -1  -1  -1  -1  11 

[ 6 4 3 1 ] 4 3 2 1

The max size is therefore 11 and possible item combinations are:

6 4 3 1 and
4 3 2 1

01 Knapsack Problem : Finding a solution through Dynamic Programming [Java][01Knapsack][Dynamic Programming]

This program finds a solution for a given 01 Knapsack Problem. The solution is based on Dynamic programming. So the time complexity for this program is O(nW). n is the number of items and W is the maximum size of the knapsack. This algorithm is more efficient than the one that uses brute force (checking all the possible combinations). That one has a complexity of O(2^n) [exponential].

Code:

import java.util.Arrays;
import java.util.Scanner;

public class Knapsack01Dynamic {

    int[][] table;
    int[] weight;
    int[] benefit;
    int capacityKnapsack;
    int nItems;

    Scanner scan = new Scanner(System.in);

    int B(int items, int maxCapacity) {

        if (maxCapacity < 0 || items < 0) {
            return -2;
        }

        if (table[items][maxCapacity] != -1) {
            return table[items][maxCapacity];
        }

        int arg1 = B(items - 1, maxCapacity);
        int arg2 = B(items - 1, (maxCapacity - weight[items - 1]));
        if (arg2 == -2) {
            arg2 = 0;
        } else {
            arg2 += benefit[items - 1];
        }
        table[items][maxCapacity] = Math.max(arg1, arg2);
        return table[items][maxCapacity];
    }

    void printItems() {
        System.out.println("Max benefit: "+table[nItems][capacityKnapsack]);
        System.out.println("Items in the knapsack: ");
        int row = capacityKnapsack;
        for (int i = nItems; i > 0; --i) {

            if (table[i][row] != table[i - 1][row]) {
                System.out.print(i+" ");
                row -= weight[i - 1];
            }
        }
    }   
    
    void input() {
        System.out.println("Enter the number of items: ");
        nItems = scan.nextInt();

        System.out.println("Enter the (weight and benefit)s of the n items: ");

        weight = new int[nItems];
        benefit = new int[nItems];

        for (int i = 0; i < nItems; ++i) {
            weight[i] = scan.nextInt();
            benefit[i] = scan.nextInt();
        }

        System.out.println("Max capacity of the knapsack: ");
        capacityKnapsack = scan.nextInt();
        table = new int[nItems + 1][capacityKnapsack + 1];

        for (int i = 1; i < nItems + 1; ++i) {
            Arrays.fill(table[i], -1);
        } 
        for (int i = 0; i < nItems + 1; ++i) {
            table[i][0] = 0;
        }
    }

    void printTable() {
        System.out.println();
        System.out.print("   ");
        int count = 0;
        for (int i = 0; i < capacityKnapsack + 1; ++i) {
            System.out.printf("%3d ", i);
        }
        System.out.println("\n");
        for (int i = 0; i < nItems + 1; ++i) {
            System.out.printf("%-3d", count);
            for (int j = 0; j < capacityKnapsack + 1; ++j) {
                System.out.printf("%1$3d ", table[i][j]);
            }
            count++;
            System.out.println();
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        Knapsack01Dynamic kd = new Knapsack01Dynamic();
        kd.input();
        kd.B(kd.nItems, kd.capacityKnapsack);
        kd.printTable(); 
        kd.printItems();
    }
}

Sample Output :

Enter the number of items:
4
Enter the (weight and benefit)s of the n items:
2 3
3 4
4 5
5 6
Max capacity of the knapsack:
5

     0   1   2   3   4   5

0    0   0   0   0   0   0
1    0   0   3  -1  -1   3
2    0   0  -1  -1  -1   7
3    0  -1  -1  -1  -1   7
4    0  -1  -1  -1  -1   7

Max benefit: 7
Items in the knapsack:
2 1