Sunday, July 27, 2014
Today in this article I will show you how to solve 01 Knapsack problem using the concept of dynamic programming in Java. This problem can also be solved by recursion but the problem is that it will result in solving of already solved subproblem. So we will be using dynamic programming to solve by storing the results of solved subproblems. Also this technique can be used to solve the problem in polynomial time. The complexity of solving it using this algorithm is O(n*W).
What is 0/1 Knapsack problem ?
The knapsack or rucksack problem is a problem in combinatorial optimization. Here there are a set of items(n) which has a profit value(v) and weight(w). There is a bag which has a maximum capacity(W). Now the problem is to fill the bag with the following restrictions :
1. You can either choose an item completely or reject it. (0 or 1)
2. The total weight of bag must not exceed its maximum capacity W. i.e. (Sum of w[i]) <= W
3. The total value or profit of items chosen must be maximum. i.e. Sum of p[i] is maximum
where 0 < i <=n.
How to solve 0/1 Knapsack problem in Java ?
Step1: Structure: Characterize the structure of an optimal solution.
– Decompose the problem into smaller problems, and ﬁnd a relation between the structure of the optimal solution of the original problem and the solutions of the smaller problems.
Step2: Principle of Optimality: Recursively deﬁne the value of an optimal solution.
– Express the solution of the original problem in terms of optimal solutions for smaller problems.
Step 3: Bottomup computation: Compute the value of an optimal solution in a bottomup fashion by using a table structure.
Step 4: Construction of optimal solution: Construct an optimal solution from computed information.
DOWNLOAD the source from Mediafire
DOWNLOAD the source from 4shared
What is 0/1 Knapsack problem ?
The knapsack or rucksack problem is a problem in combinatorial optimization. Here there are a set of items(n) which has a profit value(v) and weight(w). There is a bag which has a maximum capacity(W). Now the problem is to fill the bag with the following restrictions :
1. You can either choose an item completely or reject it. (0 or 1)
2. The total weight of bag must not exceed its maximum capacity W. i.e. (Sum of w[i]) <= W
3. The total value or profit of items chosen must be maximum. i.e. Sum of p[i] is maximum
where 0 < i <=n.
How to solve 0/1 Knapsack problem in Java ?
Step1: Structure: Characterize the structure of an optimal solution.
– Decompose the problem into smaller problems, and ﬁnd a relation between the structure of the optimal solution of the original problem and the solutions of the smaller problems.
Step2: Principle of Optimality: Recursively deﬁne the value of an optimal solution.
– Express the solution of the original problem in terms of optimal solutions for smaller problems.
Step 3: Bottomup computation: Compute the value of an optimal solution in a bottomup fashion by using a table structure.
Step 4: Construction of optimal solution: Construct an optimal solution from computed information.

Java Source Code

import java.util.Scanner; public class Knapsack { private int n,W; //number of items and maximum capacity private int w[],v[]; //weights and values of items private int V[][]; //table to store results of subproblems /** * Takes necessary inputs and initializes for solving */ private void initialize(){ Scanner sc = new Scanner(System.in); System.out.print("Enter number of items : "); n = sc.nextInt(); //number of items System.out.print("Enter W of knapsack : "); W = sc.nextInt(); //capacity of knapsack w = new int[n]; v = new int[n]; System.out.println("Enter ws and vs of items : "); for(int i = 0; i < n; i++){ w[i] = sc.nextInt(); //weight of item v[i] = sc.nextInt(); //profit of item } V = new int[n+1][W+1]; //initializing the table to hold results for(int i = 0; i <= W; i++) V[0][i] = 0; } /** * Computes the result */ public void knapsack(){ //table for backtracking to get the items chosen int x[][] = new int[n+1][W+1]; //filling tables for(int i = 1; i <= n; i++) for(int j = 0; j <= W; j++) if((w[i1] <= j) && (v[i1]+V[i1][jw[i1]] > V[i1][j])){ V[i][j] = v[i1] + V[i1][jw[i1]]; x[i][j] = 1; } else{ V[i][j] = V[i1][j]; x[i][j] = 0; } //backtracking System.out.printf("Items Chosen\n%5s%7s%7s\n", "Item","Weight","Profit"); int K = W; for(int i = n; i >= 1; i) if(x[i][K] == 1){ System.out.printf("%5d%7d%7d\n",i,w[i1],v[i1]); K = w[i1]; } System.out.println("Maximum profit : "+V[n][W]); } public static void main(String[] args) { Knapsack obj = new Knapsack(); obj.initialize(); obj.knapsack(); } }
Download Links
DOWNLOAD the source from Mediafire
DOWNLOAD the source from 4shared
Labels:Algorithms
Subscribe to:
Post Comments
(Atom)
Labels
 Algorithms (7)
 Annotation (3)
 Files (6)
 Generics (3)
 Graphics2D (5)
 Graphics2DImages (7)
 Inheritance (2)
 J2EE (9)
 Java 8 (4)
 Java FAQs (19)
 JDBC (3)
 Networking (2)
 Packages (1)
 Reflection (4)
 Security (7)
 Sorting (2)
 Swing (3)
 Threads (3)
 Utils (3)
Popular Posts

Today I will show you how you can implement Bankers algorithm in Java. The Banker's algorithm is a resource allocation and deadlock a...

 UPDATE  I have updated the code on request of some followers so that they can directly...

Today I am going to show how to convert a postfix expression to an infix expression using stack in Java. In an earlier post here we ...

Today in this article I will tell you how to convert an infix expression to postfix expression using stack. This is an important applicat...

UPDATE I have updated my post so that now it can detect IE 11. This modification was necessary as t...

Today I am going to show you how you can generate and validate captcha. A CAPTCHA (an acronym for "Completely Automated Public Turin...

Today I am going to post a program that will be able to produce all the mColorings of a given graph G. What is mColoring : The problem st...

Today I will show you how to do 256bits AES encryption and decryption of a file in Java. You can write codes for AES  128bits without d...
Links
About Me

Nirupam Das
 I am a student of BTech Computer Science Engineering from RCCIIT,Kolkata. I am a crazy lover of Java and wants to settle as a Java developer. I have a seven years Java experience with an application developer experience for 2 years. Recently from March 2012 I am a registered S40 app developer for Nokia and has corrected an app of them. I am currently writing blogs to encourage and grow interest in all those who don't know or learning Java.
thank you, it is really help me
ReplyDelete