Sunday, July 27, 2014
Today in this article I will show you how to solve 0-1 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 sub-problem. So we will be using dynamic programming to solve by storing the results of solved sub-problems. 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 find a relation between the structure of the optimal solution of the original problem and the solutions of the smaller problems.
Tuesday, July 22, 2014

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 ahve shown how to convert an infix expression to postfix using stack. Here we will just try to do the reverse. Here in our example we will be able to convert any postfix expression to infix irrespective of the operators. A number of parenthesis may be generated extra which were not there in original infix expression. The parenthesis that may be generated extra will have no impact on actual expression, they are just for better understanding. The process of postfix to infix conversion is summarised below -
Saturday, July 12, 2014
Today I am going to deal with an e3xcellent feature of the Java Concurrency framework. You can consider it as one of the most basic things of the framework. Here I will show you how to use the Executor with a simple demo example. You would like to know why to use Executor? Earlier you must have learnt during your basic learning on Java threads, that whenever you will have to do multi-threading you will have to create a task either implementing Runnable interface or extending Thread class. Then you would have to start the thread created by calling start() method. This is actually very low-level implementation where you are dealing with threads. This is completely alright for small applications. But when you are handling large applications, you would never like to handle and manage threads directly, as your main work is to deal with the task properly and concentrate on that. So keeping that in mind, her comes the advantage of Executor where you only have to create the task and
Saturday, July 5, 2014
Today I am going to discuss with the first step of JPA - Java Persistence API. JPA helps you in object-relational mapping and reduces a lot of task of coders, otherwise they have to write a lot of JDBC codes. All those things are done automatically by the Persistence provider. Throughout all the topics related to JPA that we will cover will consider EclipseLink as the JPA provider.
    After all necessary setups, the first thing you will have to do is to write a JPA entity. Many IDE like Eclipse can automatically create it, but we will show how to write it and what are the steps. You must have seen the JavaBean style classes. Here our first task is to write a class in that style only. Next we will make some modifications to make it a JPA entity.

Total Pageviews

Followers


Labels

Popular Posts

free counters