Java Program to Solve Knapsack Problem Using Dynamic Programming

This is java program to implement Knapsack problem using Dynamic programming.Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. Consider all subsets of items and calculate the total weight and value of all subsets. Consider the only subsets whose total weight is smaller than W. From all such subsets, pick the maximum value subset.

Here is the source code of the Java Program to Solve Knapsack Problem Using Dynamic Programming. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. //This is the java program to implement the knapsack problem using Dynamic Programming
  2. import java.util.Scanner;
  3.  
  4. public class Knapsack_DP 
  5. {
  6.     static int max(int a, int b) 
  7.     { 
  8.         return (a > b)? a : b; 
  9.     }
  10.     static int knapSack(int W, int wt[], int val[], int n)
  11.     {
  12.         int i, w;
  13.         int [][]K = new int[n+1][W+1];
  14.  
  15. 	   // Build table K[][] in bottom up manner
  16.         for (i = 0; i <= n; i++)
  17.         {
  18.             for (w = 0; w <= W; w++)
  19.             {
  20.                 if (i==0 || w==0)
  21.                     K[i][w] = 0;
  22.                 else if (wt[i-1] <= w)
  23.                     K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]);
  24.                 else
  25.                     K[i][w] = K[i-1][w];
  26.             }
  27.         }
  28.  
  29.         return K[n][W];
  30.     }
  31.  
  32.     public static void main(String args[])
  33.     {
  34.         Scanner sc = new Scanner(System.in);
  35.         System.out.println("Enter the number of items: ");
  36.         int n = sc.nextInt();
  37.         System.out.println("Enter the items weights: ");
  38.         int []wt = new int[n];
  39.         for(int i=0; i<n; i++)
  40.             wt[i] = sc.nextInt();
  41.  
  42.         System.out.println("Enter the items values: ");
  43.         int []val = new int[n];
  44.         for(int i=0; i<n; i++)
  45.             val[i] = sc.nextInt();
  46.  
  47.         System.out.println("Enter the maximum capacity: ");
  48.         int W = sc.nextInt();
  49.  
  50.         System.out.println("The maximum value that can be put in a knapsack of capacity W is: " + knapSack(W, wt, val, n));
  51.         sc.close();
  52.     }
  53. }

Output:

$ javac Knapsack_DP.java
$ java Knapsack_DP
 
Enter the number of items: 
5
Enter the items weights: 
01 56 42 78 12
Enter the items values: 
50 30 20 10 50 
Enter the maximum capacity: 
150
The maximum value that can be put in a knapsack of capacity W is: 150

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.