Skip to content

Commit f0886c3

Browse files
UtkarshsteveUtkarshsteve
committed
Knapsack Problem Using Dynamic Programming and Greedy Method
1 parent 6217568 commit f0886c3

7 files changed

Lines changed: 387 additions & 0 deletions

File tree

‎Knapsack/KObject.class‎

235 Bytes
Binary file not shown.

‎Knapsack/KnapsackDP‎

Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,87 @@
1+
import java.util.Scanner;
2+
3+
public class KnapsackDP
4+
{
5+
6+
static final int MAX=20; //max no. of objects
7+
static int w[]; //weights 0 to n-1
8+
static int p[]; //profits 0 to n-1
9+
static int n; //no. of objects
10+
static int M; //capacity of Knapsack
11+
static int V[][]; //Dyamic Programming process-table
12+
static int Keep[][]; //to get objects in optimal solution
13+
14+
public static void main(String args[])
15+
{
16+
17+
w=new int[MAX];
18+
p=new int[MAX];
19+
V=new int[MAX][MAX];
20+
Keep=new int[MAX][MAX];
21+
int optsoln;
22+
ReadObjects();
23+
for(int i=0;i<=M;i++)
24+
V[0][i]=0;
25+
for(int i=0;i<=n;i++)
26+
V[i][0]=0;
27+
optsoln=Knapsack();
28+
System.out.println("Optimal Solution = " + optsoln);
29+
30+
31+
}
32+
33+
static int Knapsack()
34+
{
35+
36+
int r; //remaining Knapsack capacity
37+
for(int i=1;i<=n;i++)
38+
for(int j=0;j<=M;j++)
39+
if((w[i]<=j)&&(p[i]+V[i-1][j-w[i]]>V[i-1][j]))
40+
{
41+
42+
V[i][j]=p[i]+V[i-1][j-w[i]];
43+
Keep[i][j]=1;
44+
45+
}
46+
47+
else
48+
{
49+
50+
V[i][j]=V[i-1][j];
51+
Keep[i][j]=0;
52+
53+
}
54+
55+
56+
//Find the objects included in the Knapsack
57+
r=M;
58+
System.out.println("Items=");
59+
for(int i=n;i>0;i--) //start from Keep[n,M]
60+
if(Keep[i][r]==1)
61+
{
62+
63+
System.out.println(i+" ");
64+
r=r-w[i];
65+
66+
}
67+
System.out.println();
68+
return V[n][M];
69+
}
70+
71+
static void ReadObjects()
72+
{
73+
74+
Scanner sc=new Scanner(System.in);
75+
System.out.println("Knapsack Problem - Dynamic Programming Solution:");
76+
System.out.println("Enter the max capacity of knapsack:");
77+
M=sc.nextInt();
78+
System.out.println("Enter Weights: ");
79+
for(int i=1;i<=n;i++)
80+
w[i]=sc.nextInt();
81+
System.out.println("Enter Profits:");
82+
for(int i=1;i<=n;i++)
83+
p[i]=sc.nextInt();
84+
sc.close();
85+
86+
}
87+
}

‎Knapsack/KnapsackDP.class‎

2.19 KB
Binary file not shown.

‎Knapsack/KnapsackDP.java‎

Lines changed: 89 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,89 @@
1+
import java.util.Scanner;
2+
3+
public class KnapsackDP
4+
{
5+
6+
static final int MAX=20; //max no. of objects
7+
static int w[]; //weights 0 to n-1
8+
static int p[]; //profits 0 to n-1
9+
static int n; //no. of objects
10+
static int M; //capacity of Knapsack
11+
static int V[][]; //Dyamic Programming process-table
12+
static int Keep[][]; //to get objects in optimal solution
13+
14+
public static void main(String args[])
15+
{
16+
17+
w=new int[MAX];
18+
p=new int[MAX];
19+
V=new int[MAX][MAX];
20+
Keep=new int[MAX][MAX];
21+
int optsoln;
22+
ReadObjects();
23+
for(int i=0;i<=M;i++)
24+
V[0][i]=0;
25+
for(int i=0;i<=n;i++)
26+
V[i][0]=0;
27+
optsoln=Knapsack();
28+
System.out.println("Optimal Solution = " + optsoln);
29+
30+
31+
}
32+
33+
static int Knapsack()
34+
{
35+
36+
int r; //remaining Knapsack capacity
37+
for(int i=1;i<=n;i++)
38+
for(int j=0;j<=M;j++)
39+
if((w[i]<=j)&&(p[i]+V[i-1][j-w[i]]>V[i-1][j]))
40+
{
41+
42+
V[i][j]=p[i]+V[i-1][j-w[i]];
43+
Keep[i][j]=1;
44+
45+
}
46+
47+
else
48+
{
49+
50+
V[i][j]=V[i-1][j];
51+
Keep[i][j]=0;
52+
53+
}
54+
55+
56+
//Find the objects included in the Knapsack
57+
r=M;
58+
System.out.print("Items=");
59+
for(int i=n;i>0;i--) //start from Keep[n,M]
60+
if(Keep[i][r]==1)
61+
{
62+
63+
System.out.println(i+" ");
64+
r=r-w[i];
65+
66+
}
67+
System.out.println();
68+
return V[n][M];
69+
}
70+
71+
static void ReadObjects()
72+
{
73+
74+
Scanner sc=new Scanner(System.in);
75+
System.out.println("Knapsack Problem - Dynamic Programming Solution:");
76+
System.out.println("Enter the max capacity of knapsack:");
77+
M=sc.nextInt();
78+
System.out.println("Enter number of objects:");
79+
n=sc.nextInt();
80+
System.out.println("Enter Weights: ");
81+
for(int i=1;i<=n;i++)
82+
w[i]=sc.nextInt();
83+
System.out.println("Enter Profits:");
84+
for(int i=1;i<=n;i++)
85+
p[i]=sc.nextInt();
86+
sc.close();
87+
88+
}
89+
}

‎Knapsack/KnapsackGreedy‎

Lines changed: 105 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,105 @@
1+
import java.util.Scanner;
2+
3+
class KObject { //Knapsack Object Details
4+
5+
float w;
6+
float p;
7+
float r;
8+
}
9+
10+
public class KnapsackGreedy
11+
{
12+
13+
static final int MAX=20; //Maximum no. of objects
14+
static int n; //no. of objects
15+
static float M; //capacity of Knapsack
16+
17+
public static void main(String args[]) {
18+
19+
Scanner sc=new Scanner(System.in);
20+
System.out.println("Enter no. of Objects:");
21+
n=sc.nextInt();
22+
KObject[] obj =new KObject[n];
23+
for(int i=0;i<n;i++)
24+
obj[i]=new KObject(); //allocate memory for members
25+
26+
ReadObjects(obj);
27+
Knapsack(obj)
28+
29+
30+
}
31+
32+
static void ReadObjects(KObject obj[])
33+
{
34+
35+
KObject temp=new KObject();
36+
Scanner sc = new Scanner(System.in);
37+
System.out.println("Enter the max capacity of knapsack:");
38+
M=sc.nextFloat();
39+
40+
System.out.println("Enter weights:");
41+
for(int i=0;i<n;i++)
42+
obj[i].w=sc.nextFloat();
43+
44+
System.out.println("Enter Profits:");
45+
for(int i=0;i<n;i++)
46+
obj[i].p=sc.nextFloat();
47+
48+
for(int i=0;i<n;i++)
49+
obj[i].r=obj[i].p/obj[i].w;
50+
51+
//sort objects in descending order, based on p/w ratio
52+
for(int i=0;i<n-1;i++)
53+
for(int j=0;j<n-1-i;j++)
54+
if(obj[j].r<obj[j+1].r)
55+
{
56+
57+
temp=obj[j];
58+
obj[j]=obj[j+];
59+
obj[j+]=temp;
60+
61+
}
62+
sc.close();
63+
64+
}
65+
66+
static void Knapsack(KObject kobj[])
67+
{
68+
69+
float x[] = new float[MAX];
70+
float tp=0;
71+
int i;
72+
float U; //U place holder for M
73+
U=M;
74+
75+
for(i=0;i<n;i++)
76+
x[i]=0;
77+
for(i=0;i<n;i++)
78+
{
79+
80+
if(kobj[i].w>U)
81+
break;
82+
83+
else
84+
{
85+
86+
x[i]=1;
87+
tp=tp+kobj[i].p;
88+
U=U-kobj[i].w;
89+
90+
91+
}
92+
93+
}
94+
System.out.println("i= "+i);
95+
if(i<n)
96+
x[i]=U/kobj[i].w;
97+
tp=tp+(x[i]*kobj[i].p);
98+
System.out.println("The Solution Vector, x[]:");
99+
for(i=0;i<n;i++)
100+
System.out.println(x[i]+"");
101+
System.out.println("\n Total Profit is = "+tp);
102+
}
103+
104+
}
105+

‎Knapsack/KnapsackGreedy.class‎

2.3 KB
Binary file not shown.

‎Knapsack/KnapsackGreedy.java‎

Lines changed: 106 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,106 @@
1+
import java.util.Scanner;
2+
3+
class KObject { //Knapsack Object Details
4+
5+
float w;
6+
float p;
7+
float r;
8+
}
9+
10+
public class KnapsackGreedy
11+
{
12+
13+
static final int MAX=20; //Maximum no. of objects
14+
static int n; //no. of objects
15+
static float M; //capacity of Knapsack
16+
17+
public static void main(String args[]) {
18+
19+
Scanner sc=new Scanner(System.in);
20+
System.out.println("Enter no. of Objects:");
21+
n=sc.nextInt();
22+
KObject[] obj =new KObject[n];
23+
for(int i=0;i<n;i++)
24+
obj[i]=new KObject(); //allocate memory for members
25+
26+
ReadObjects(obj);
27+
Knapsack(obj);
28+
sc.close();
29+
30+
31+
}
32+
33+
static void ReadObjects(KObject obj[])
34+
{
35+
36+
KObject temp=new KObject();
37+
Scanner sc = new Scanner(System.in);
38+
System.out.println("Enter the max capacity of knapsack:");
39+
M=sc.nextFloat();
40+
41+
System.out.println("Enter weights:");
42+
for(int i=0;i<n;i++)
43+
obj[i].w=sc.nextFloat();
44+
45+
System.out.println("Enter Profits:");
46+
for(int i=0;i<n;i++)
47+
obj[i].p=sc.nextFloat();
48+
49+
for(int i=0;i<n;i++)
50+
obj[i].r=obj[i].p/obj[i].w;
51+
52+
//sort objects in descending order, based on p/w ratio
53+
for(int i=0;i<n-1;i++)
54+
for(int j=0;j<n-1-i;j++)
55+
if(obj[j].r<obj[j+1].r)
56+
{
57+
58+
temp=obj[j];
59+
obj[j]=obj[j+1];
60+
obj[j+1]=temp;
61+
62+
}
63+
sc.close();
64+
65+
}
66+
67+
static void Knapsack(KObject kobj[])
68+
{
69+
70+
float x[] = new float[MAX];
71+
float tp=0;
72+
int i;
73+
float U; //U place holder for M
74+
U=M;
75+
76+
for(i=0;i<n;i++)
77+
x[i]=0;
78+
for(i=0;i<n;i++)
79+
{
80+
81+
if(kobj[i].w>U)
82+
break;
83+
84+
else
85+
{
86+
87+
x[i]=1;
88+
tp=tp+kobj[i].p;
89+
U=U-kobj[i].w;
90+
91+
92+
}
93+
94+
}
95+
System.out.println("i= "+i);
96+
if(i<n)
97+
x[i]=U/kobj[i].w;
98+
tp=tp+(x[i]*kobj[i].p);
99+
System.out.println("The Solution Vector, x[]:");
100+
for(i=0;i<n;i++)
101+
System.out.println(x[i]+"");
102+
System.out.println("\n Total Profit is = "+tp);
103+
}
104+
105+
}
106+

0 commit comments

Comments
 (0)