The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight 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 useful items.
In the following, we have n kinds of items, 1 through n. Each kind of item i has a value vi and a weight wi. We usually assume that all values and weights are nonnegative. To simplify the representation, we can also assume that the items are listed in increasing order of weight. The maximum weight that we can carry in the bag is W.
The most common formulation of the problem is the 0-1 knapsack problem, which restricts the number xi of copies of each kind of item to zero or one. Mathematically the 0-1-knapsack problem can be formulated as:
maximize sum(vi,xi) for i=0 to n
such that sum(wi*xi)<=W & x(0,1)
The unbounded knapsack problem (UKP) places no upper bound on the number of copies of each kind of item.
Of particular interest is the special case of the problem with these properties:
it is a decision problem,
it is a 0-1 problem,
for each kind of item, the weight equals the value: wi = vi.
Notice that in this special case, the problem is equivalent to this: given a set of nonnegative integers, does any subset of it add up to exactly W? Or, if negative weights are allowed and W is chosen to be zero, the problem is: given a set of integers, does any nonempty subset add up to exactly 0? This special case is called the subset sum problem. In the field of cryptography the term knapsack problem is often used to refer specifically to the subset sum problem.\
Dynamic Programming Solution:
Unbounded knapsack problem
If all weights () are nonnegative integers, the knapsack problem can be solved in pseudo-polynomial time using dynamic programming. The following describes a dynamic programming solution for the unbounded knapsack problem.
To simplify things, assume all weights are strictly positive (wi > 0). We wish to maximize total value subject to the constraint that total weight is less than or equal to W. Then for each w ≤ W, define m[w] to be the maximum value that can be attained with total weight less than or equal to w. m[W] then is the solution to the problem.
Observe that m[w] has the following properties:
m[0]=0 (the sum of zero items, i.e., the summation of the empty set)
m[i]=max(m[w-1],vi+m[w-wi]) where wi<=w
where vi is the value of the i-th kind of item.
Here the maximum of the empty set is taken to be zero. Tabulating the results from m[0] up through m[W] gives the solution. Since the calculation of each m[w] involves examining n items, and there are W values of m[w] to calculate, the running time of the dynamic programming solution is O(nW). Dividing by their greatest common divisor is an obvious way to improve the running time.
Working Code:
import java.io.*;
class knapsack10
{
public static void main(String args[]) throws IOException
{
int capacity,n;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println ("\n Enter the number of items u want to enter:");
n= Integer.parseInt(br.readLine());
float p[]=new float[n+1];
float x[]=new float[n+1];
int i,j,k,w;
int WEIGHT[]=new int[n+1],PROFIT[]=new int[n+1];
WEIGHT[0]=0;
PROFIT[0]=0;
for(i=1;i<=n;i++)
{
System.out.println ("\n Enter the weight and profit of "+i+" : item ");
WEIGHT[i]= Integer.parseInt(br.readLine());
PROFIT[i]= Integer.parseInt(br.readLine());
p[i]=0;
x[i]=0;
}
System.out.println ("\n Enter the capacity of the knapsack : ");
capacity = Integer.parseInt(br.readLine());
float c[][]=new float [n+1][capacity+1];
for(i=0;i<=n;i++)
for(j=0;j<=capacity;j++)
c[i][j] = 0;
for(i=1;i<=n;i++)
for(w=1;w<=capacity;w++)
if(WEIGHT[i]<=w){
if ((PROFIT[i]+c[i-1][w-WEIGHT[i]])>c[i-1][w])
{
c[i][w] = PROFIT[i] + c[i-1][w-WEIGHT[i]];
p[i] = 1;
}
else
{
c[i][w]=c[i-1][w];
p[i] = 0;
}}
else
{
c[i][w]=c[i-1][w];
p[i] = 0;
}
float temp=0;
int t=0;
for(j=1;j<=capacity;j++)
{
temp = c[n-1][j]-c[n-1][j-1];
for(i=1;i
if(temp==PROFIT[i])
t=i;
x[t] = 1;
}
for(j=0;j<=n;j++)
System.out.println (j+" "+x[j] );
System.out.println ("The profit obtained is "+c[n][capacity]);
}
}
The O(nW) complexity does not contradict the fact that the knapsack problem is NP-complete, since W, unlike n, is not polynomial in the length of the input to the problem. The length of the W input to the problem is proportional to the number of bits in W, logW, not to W itself.
Time Complexity O(NlogN) W<=logW
Space Complexity (N^2)
More Info.
www.es.ele.tue.nl/education/5MC10/Solutions/knapsack.pdf
www.cse.unl.edu/~goddard/Courses/CSCE310J/Lectures/Lecture8-DynamicProgramming.pdf
2nd Knapsack 0/1 Problem(In Progress)
