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.
//This is the java program to implement the knapsack problem using Dynamic Programming import java.util.Scanner; public class Knapsack_DP { static int max(int a, int b) { return (a > b)? a : b; } static int knapSack(int W, int wt[], int val[], int n) { int i, w; int [][]K = new int[n+1][W+1]; // Build table K[][] in bottom up manner for (i = 0; i <= n; i++) { for (w = 0; w <= W; w++) { if (i==0 || w==0) K[i][w] = 0; else if (wt[i-1] <= w) K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]); else K[i][w] = K[i-1][w]; } } return K[n][W]; } public static void main(String args[]) { Scanner sc = new Scanner(System.in); System.out.println("Enter the number of items: "); int n = sc.nextInt(); System.out.println("Enter the items weights: "); int []wt = new int[n]; for(int i=0; i<n; i++) wt[i] = sc.nextInt(); System.out.println("Enter the items values: "); int []val = new int[n]; for(int i=0; i<n; i++) val[i] = sc.nextInt(); System.out.println("Enter the maximum capacity: "); int W = sc.nextInt(); System.out.println("The maximum value that can be put in a knapsack of capacity W is: " + knapSack(W, wt, val, n)); sc.close(); } }
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
Related posts:
Java Program to Check Whether a Weak Link i.e. Articulation Vertex Exists in a Graph
Java – InputStream to Reader
Java Program to Implement the linear congruential generator for Pseudo Random Number Generation
Spring Boot - Runners
Java Program to Implement ArrayDeque API
A Guide to Java 9 Modularity
A Guide to EnumMap
Jackson Unmarshalling JSON with Unknown Properties
Spring Boot Integration Testing with Embedded MongoDB
Logout in an OAuth Secured Application
Java Program to Perform Naive String Matching
Working with Kotlin and JPA
A Guide To UDP In Java
Spring Boot - Cloud Configuration Client
Versioning a REST API
New Features in Java 10
Mảng (Array) trong Java
Spring Boot Change Context Path
Sort a HashMap in Java
A Quick Guide to Using Keycloak with Spring Boot
Convert String to int or Integer in Java
Java – Write an InputStream to a File
Java Program to Implement Multi-Threaded Version of Binary Search Tree
Creating Docker Images with Spring Boot
Sử dụng CountDownLatch trong Java
Removing all duplicates from a List in Java
Query Entities by Dates and Times with Spring Data JPA
Introduction to Spring Data JPA
Spring Boot Gradle Plugin
Split a String in Java
Serverless Functions with Spring Cloud Function
A Guide to Concurrent Queues in Java