Conduct an empirical study of several algorithms for the 0/1 Knapsack problem in

Question

Conduct an empirical study of several algorithms for the 0/1 Knapsack problem in Java. The 0/1 Knapsack problem is defined as follows: given a set S of n objects, each with a weight and an value, a maximum total weight W and a minimum total value V, determine whether some subset of S has weight at most W and value at least V. You will need to write code to implement 1) a random generator for sets of objects and 2) several algorithms that solve instance of the problem. The size of the set N, the maximum weight WMAX, and the maximum value VMAX. All weights and values are positive integers, and duplicate weights and values are allowed.

Code several algorithms that include an exact bounded backtracking algorithm, an exact dynamic programming algorithm, and an exact algorithm of your own design that is as efficient as you can make it. You must also write a polynomial-time approximation algorithm that is as accurate as you can make it.

Your empirical study must include sufficient testing to establish the correctness of your exact algorithms and to compare their performance in various regions of the problem space. You should also conduct experiments to determine which problem instances are harder than others. Is there a density-based critical region in the problem space? How do the values of the constraints W and V affect the processing time? Is there a critical region associated with W and V? Do some algorithms perform better than others in different regions of the problems space? Does the accuracy of your approximation algorithm vary in different regions of the problem space?

Write a written report that describes and explains your empirical study and its results. Write your program in Java and report in word.

Explanation / Answer

package knapsackproblem;

public class KnapsackProblem {
public int picks[][];
public int matrix[][];
public int nItems;
public int knapsackSize;
public float unit[];
public int weights[];// W
public int values[]; // V
int maxCapacity;
int y[],x[];
float fp,fw;

public KnapsackProblem()
{ nItems=4;
fp=-1;
maxCapacity=100;
knapsackSize = 10;
weights=new int []{5,4,6,3};
unit=new float[weights.length];
y=new int[weights.length];
x=new int[weights.length];
values=new int []{10,40,30,50};
picks=new int [100][100];
matrix=new int[100][100];
for(int i=0;i<100;i++)
{
for(int j=0;j<100;j++)
{
picks[i][j]=0;
matrix[i][j]=0;
}
}
}
public static void main(String[] args) {
  
KnapsackProblem K=new KnapsackProblem();
System.out.println("By Dynamic Programming Algorithm");
System.out.println("Max value = "+K.DynamicProgramming(K.nItems-1, K.knapsackSize));
K.printPicks();
System.out.println("By Bounded Bactracking Algorithm");
K.BoundedBackTracking(0, 0, 0);
K.sort();
K.show();
}
  
void printPicks()
{
int item=nItems-1;
int size=knapsackSize;
System.out.println("Index of the picked items ");
while (item>=0){
if (picks[item][size]==1){
System.out.print(" "+item);
item--;
size -= weights[item];
if(size<0)
{
System.out.print(" "+item);
break;
}
}
else{
item--;
}
}
System.out.println(" ");
}
  
int max(int a, int b)
{
if(a>b)
return a;
else
return b;
}
int DynamicProgramming(int index, int size)
{
int take=0,dontTake=0;

if (matrix[index][size]!=0)
return matrix[index][size];

if (index==0){
if (weights[0]<=size){
picks[index][size]=1;
matrix[index][size] = values[0];
return values[0];
}
else{
picks[index][size]=-1;
matrix[index][size] = 0;
return 0;
}
}

if (weights[index]<=size)
take = values[index] + DynamicProgramming(index-1, size-weights[index]);

dontTake = DynamicProgramming(index-1, size);

matrix[index][size] = max (take, dontTake);
if (take>dontTake)
picks[index][size]=1;
else
picks[index][size]=-1;

return matrix[index][size];
}
void show()
{
float s=0;
int i;
System.out.println(" Item Weight Cost Unit Profit Selected ");
for(i=0;i<knapsackSize;i++)
System.out.println(" "+ (i+1)+" "+weights[i]+" "+values[i]+" "+unit[i]+" "+x[i]);
System.out.println(" The Sack now holds following items : ");
for(i=0;i<knapsackSize;i++)
if(x[i]==1)   
{
System.out.println(" "+i+1);
s += (float) values[i] * (float) x[i];   
}
System.out.println(" Maximum Profit: "+s);
}
/*Arrange the item based on high profit per Unit*/
void sort()
{
int t,t1,n=knapsackSize,i,j;
float t2;
for(i=0;i<n;i++)
unit[i] = (float)values[i] / (float)weights[i];
for(i=0;i<n-1;i++)
{   
for(j=i+1;j<n;j++)   
{
if(unit[i] < unit[j])   
{
t2 = unit[i];
unit[i] = unit[j];
unit[j] = t2;   
t = values[i];   
values[i] = values[j];
values[j] = t;
t1 = weights[i];
weights[i] = weights[j];
weights[j] =t1;
}
}   
}
}
float bound(float cp,float cw,int k)
{
int n=knapsackSize;
int m=maxCapacity;
float b = cp;
float c = cw;
int i;
for(i=k;i<=n;i++)
{
c = c+weights[i];   
if( c < m)
b = b +values[i];
else   
return (b+(1-(c-m)/ (float)weights[i])*values[i]);
}
return b;
}

void BoundedBackTracking(int k, float cp, float cw)
{
int n=knapsackSize;
int m=maxCapacity,i,j;
if(cw+weights[k] <= m)
{
y[k] = 1;
if(k <= n)
BoundedBackTracking(k+1,cp+values[k],cw+weights[k]);
if(((cp+values[k]) > fp) && ( k == n))
{
fp =cp+values[k];   
fw = cw+weights[k];
for(j=0;j<=k;j++)
x[j] = y[j];   
}   
}
if(bound(cp,cw,k) >= fp)
{
y[k] = 0;
if( k <= n)
BoundedBackTracking(k+1,cp,cw);
if((cp > fp) && (k == n))
{
fp = cp;
fw = cw;
for(j=0;j<=k;j++)   
x[j] = y[j];   
}
}
}
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.