Gready Alogorithms or knapsack algorithms

The 0-1 Knapsack problem using a recursive dynamic programming approach. It correctly calculates the maximum value that can be obtained by putting items in a knapsack with a given weight limit. Here's a brief explanation of the code:

Java

package com.kartik.knapsack; public // A Dynamic Programming based solution for 0-1 Knapsack problem class Knapsack {  // A utility function that returns maximum of two integers     static int max(int a, int b) { return (a > b)? a : b; }         // Returns the maximum value that can be put in a knapsack of capacity W     static int knapSack(int W, int wt[], int val[], int n)     {        // Base Case    if (n == 0 || W == 0)        return 0;        // If weight of the nth item is more than Knapsack capacity W, then    // this item cannot be included in the optimal solution    if (wt[n-1] > W)       return knapSack(W, wt, val, n-1);        // Return the maximum of two cases:    // (1) nth item included    // (2) not included    else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),                     knapSack(W, wt, val, n-1)                      );      }     // Driver program to test above function     public static void main(String args[])     {         int val[] = new int[]{60, 100, 120};     int wt[] = new int[]{10, 20, 30};     int  W = 50;     int n = val.length;     System.out.println(knapSack(W, wt, val, n));     } }

 

Problem Overview:

In the 0-1 Knapsack problem, you're given:

Ø  n items, each with a weight wt[i] and a value val[i].

Ø  A knapsack with a weight capacity W.

The goal is to maximize the total value of the items that can fit in the knapsack without exceeding the weight capacity. Each item can either be included or excluded (hence "0-1").

Code Breakdown:

1. Utility Function max(int a, int b):

Ø  This function simply returns the maximum of two integers. It's used to compare the value of including or excluding an item in the knapsack.

2. Recursive Function knapSack(int W, int wt[], int val[], int n):

Ø  This function recursively determines the maximum value that can be obtained with the given weight capacity W, considering n items.

Ø  Base Case: If there are no items (n == 0) or the weight capacity is zero (W == 0), the function returns 0.

Ø  Exclusion Case: If the weight of the nth item (wt[n-1]) exceeds the current capacity W, the item is excluded from the solution, and the function proceeds with the remaining n-1 items.

Ø  Inclusion/Exclusion Decision: If the item can fit, the function calculates the maximum value between:

ü  Including the nth item and reducing the capacity by its weight (W - wt[n-1]).

ü  Excluding the nth item and proceeding with the remaining items.

3. Driver Code:

Ø  The main function defines the values and weights of the items, the knapsack capacity (W), and the number of items (n). It then calls the knapSack function to compute the maximum value.

Example:

For the provided input:

Java

int val[] = new int[]{60, 100, 120};  // Values of the items int wt[] = new int[]{10, 20, 30};     // Weights of the items int W = 50;                           // Capacity of the knapsack

 

Ø  The knapsack has a capacity of 50 units.

Ø  The items have weights of 10, 20, and 30 units, with values 60, 100, and 120, respectively.

Ø  The function will calculate the maximum value that can be obtained by selecting items without exceeding the capacity.

Optimized Dynamic Programming Version:

Although the recursive solution works, it can be inefficient for large inputs due to overlapping subproblems. To optimize it, you can use a bottom-up dynamic programming approach with a table to store intermediate results, avoiding redundant calculations. Here's how you can rewrite it:

Optimized Code:

java

package com.kartik.knapsack;   public class Knapsack {       // Returns the maximum value that can be put in a knapsack of capacity W     static int knapSack(int W, int wt[], int val[], int n) {         // Create a DP table to store solutions of subproblems         int dp[][] = new int[n + 1][W + 1];           // Build the table in a bottom-up manner         for (int i = 0; i <= n; i++) {             for (int w = 0; w <= W; w++) {                 if (i == 0 || w == 0) {                     dp[i][w] = 0;  // Base case: no items or no capacity                 } else if (wt[i - 1] <= w) {                     dp[i][w] = Math.max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);                 } else {                     dp[i][w] = dp[i - 1][w];                 }             }         }           // The last cell of the table contains the answer         return dp[n][W];     }       // Driver program to test above function     public static void main(String args[]) {         int val[] = new int[]{60, 100, 120};         int wt[] = new int[]{10, 20, 30};         int W = 50;         int n = val.length;         System.out.println(knapSack(W, wt, val, n));  // Output: 220     } }

Plain text

220

 

Explanation of Optimized Version:

Ø  Dynamic Programming Table dp[i][w]:

ü  dp[i][w] represents the maximum value obtainable with i items and a knapsack capacity of w.

ü  The table is built from the bottom up, filling in values for each subproblem based on whether the item is included or excluded.

Ø  Efficiency:

ü  Time complexity: O(n * W) where n is the number of items and W is the knapsack capacity.

ü  Space complexity: O(n * W) for the DP table.

This bottom-up approach is much more efficient for larger inputs, avoiding the exponential time complexity of the recursive solution.

Gready Alogorithms or knapsack algorithms