Java Program to Solve the 0-1 Knapsack Problem

This is java program to implement 0/1 Knapsack problem. The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a mass and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.

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

  1. //This is a sample program to implement a 0/1 knapsack algorithm 
  2. import java.util.Scanner;
  3.  
  4. public class Zero_One_Knapsack
  5. {
  6.     public void solve(int[] wt, int[] val, int W, int N)
  7.     {
  8.         int NEGATIVE_INFINITY = Integer.MIN_VALUE;
  9.         int[][] m = new int[N + 1][W + 1];
  10.         int[][] sol = new int[N + 1][W + 1];
  11.         for (int i = 1; i <= N; i++)
  12.         {
  13.             for (int j = 0; j <= W; j++)
  14.             {
  15.                 int m1 = m[i - 1][j];
  16.                 int m2 = NEGATIVE_INFINITY; 
  17.                 if (j >= wt[i])
  18.                     m2 = m[i - 1][j - wt[i]] + val[i];
  19.                 m[i][j] = Math.max(m1, m2);
  20.                 sol[i][j] = m2 > m1 ? 1 : 0;
  21.             }
  22.         }        
  23.         int[] selected = new int[N + 1];
  24.         for (int n = N, w = W; n > 0; n--)
  25.         {
  26.             if (sol[n][w] != 0)
  27.             {
  28.                 selected[n] = 1;
  29.                 w = w - wt[n];
  30.             }
  31.             else
  32.                 selected[n] = 0;
  33.         }
  34.         System.out.print("\nItems with weight ");
  35.         for (int i = 1; i < N + 1; i++)
  36.             if (selected[i] == 1)
  37.                 System.out.print(val[i] +" ");
  38.         System.out.println("are selected by knapsack algorithm.");
  39.     }
  40.     public static void main (String[] args) 
  41.     {
  42.         Scanner scan = new Scanner(System.in);
  43.         Zero_One_Knapsack ks = new Zero_One_Knapsack();
  44.  
  45.         System.out.println("Enter number of elements ");
  46.         int n = scan.nextInt();
  47.  
  48.         int[] wt = new int[n + 1];
  49.         int[] val = new int[n + 1];
  50.  
  51.         System.out.println("Enter weight for "+ n +" elements");
  52.         for (int i = 1; i <= n; i++)
  53.             wt[i] = scan.nextInt();
  54.         System.out.println("Enter value for "+ n +" elements");
  55.         for (int i = 1; i <= n; i++)
  56.             val[i] = scan.nextInt();
  57.  
  58.         System.out.println("Enter knapsack weight ");
  59.         int W = scan.nextInt();
  60.  
  61.         ks.solve(wt, val, W, n);
  62.         scan.close();
  63.     }
  64. }

Output:

$ javac Zero_One_Knapsack.java
$ java Zero_One_Knapsack
 
Enter number of elements 
5
Enter weight for 5 elements
01 56 42 78 12
Enter value for 5 elements
50 30 20 10 50
Enter knapsack weight 
150
 
Items with weight 50 30 20 50 are selected by knapsack algorithm.

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.