Knapsack Algorithm

The Knapsack Algorithm is a widely used optimization technique in computer science and mathematics, particularly in the realm of combinatorial optimization. It aims to solve the Knapsack Problem, which is a classic problem that involves determining the most valuable combination of items that can be packed into a container with limited capacity, such that the total weight of the items does not exceed the container's weight limit. The algorithm seeks to maximize the overall value or benefit obtained from the items while adhering to the given weight constraints. The Knapsack Problem has numerous practical applications in areas such as logistics, finance, and resource allocation. There are various approaches to solving the Knapsack Problem, including greedy algorithms, dynamic programming, and branch-and-bound methods. The most common approach is the dynamic programming method, which breaks down the problem into smaller overlapping subproblems and builds a solution iteratively from the bottom up. This approach utilizes a table to store the solutions to subproblems, enabling efficient reuse of previously computed results and reducing the overall time complexity. The Knapsack Algorithm is especially useful in cases where exact solutions are required, as opposed to approximate solutions provided by heuristic methods. However, the Knapsack Problem is classified as NP-hard, meaning that finding an exact solution can become computationally intractable for large-scale instances of the problem.
package DynamicProgramming;

/**
 * A DynamicProgramming based solution for 0-1 Knapsack problem
 */

public class Knapsack {

    private static int knapSack(int W, int wt[], int val[], int n) throws IllegalArgumentException {
        if(wt == null || val == null)
            throw new IllegalArgumentException();
        int i, w;
        int rv[][] = new int[n + 1][W + 1];    //rv means return value

        // Build table rv[][] in bottom up manner
        for (i = 0; i <= n; i++) {
            for (w = 0; w <= W; w++) {
                if (i == 0 || w == 0)
                    rv[i][w] = 0;
                else if (wt[i - 1] <= w)
                    rv[i][w] = Math.max(val[i - 1] + rv[i - 1][w - wt[i - 1]], rv[i - 1][w]);
                else
                    rv[i][w] = rv[i - 1][w];
            }
        }

        return rv[n][W];
    }


    // Driver program to test above function
    public static void main(String args[]) {
        int val[] = new int[]{50, 100, 130};
        int wt[] = new int[]{10, 20, 40};
        int W = 50;
        int n = val.length;
        System.out.println(knapSack(W, wt, val, n));
    }
}

LANGUAGE:

DARK MODE: