Vidyavardhaka College of Engineering
Gokulam III stage, Mysuru – 570 002
Autonomous Institute under Visvesvaraya Technological University (VTU)
Accredited by NBA (2020- 2023) & NAAC with ‘A’ Grade (2018 - 2023)
/* Program 7
Implement 0/1 Knapsack problem using Dynamic Programming.
*/
import [Link];
public class KnapsackDP {
static final int MAX = 20; // max. no. of objects
static int w[]; // weights 0 to n-1
static int p[]; // profits 0 to n-1
static int n; // no. of objects
static int M; // capacity of Knapsack
static int V[][]; // DP solution process - table
static int Keep[][]; // to get objects in optimal solution
public static void main(String args[]) {
w = new int[MAX];
p = new int[MAX];
V = new int [MAX][MAX];
Keep = new int[MAX][MAX];
int optsoln;
[Link]("*****KNAPSACK USING DYNAMIC PROGRAMMING*****");
ReadObjects();
for (int i = 0; i <= M; i++)
V[0][i] = 0;
for (int i = 0; i <= n; i++)
V[i][0] = 0;
optsoln = Knapsack();
[Link]("Optimal solution (Maximum Profit) = " + optsoln);
}
static int Knapsack() {
int r; // remaining Knapsack capacity
for (int i = 1; i <= n; i++)
for (int j = 0; j <= M; j++)
if ((w[i] <= j) && (p[i] + V[i - 1][j - w[i]] > V[i - 1][j])) {
V[i][j] = p[i] + V[i - 1][j - w[i]];
Keep[i][j] = 1;
} else {
V[i][j] = V[i - 1][j];
Keep[i][j] = 0;
}
// Find the objects included in the Knapsack
r = M;
[Link]("Items selected are = ");
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
Department of IS&E 16 VVCE, Mysoru - 02
Vidyavardhaka College of Engineering
Gokulam III stage, Mysuru – 570 002
Autonomous Institute under Visvesvaraya Technological University (VTU)
Accredited by NBA (2020- 2023) & NAAC with ‘A’ Grade (2018 - 2023)
for (int i = n; i > 0; i--) // start from Keep[n,M]
if (Keep[i][r] == 1) {
[Link](i + " ");
r = r - w[i];
}
[Link]();
return V[n][M];
}
static void ReadObjects() {
Scanner scanner = new Scanner([Link]);
[Link]("Enter number of objects: ");
n = [Link]();
[Link]("Enter the max capacity of knapsack: ");
M = [Link]();
[Link]("Enter Weights: ");
for (int i = 1; i <= n; i++)
w[i] = [Link]();
[Link]("Enter Profits: ");
for (int i = 1; i <= n; i++)
p[i] = [Link]();
[Link]();
}
}
OUTPUT:
*****KNAPSACK USING DYNAMIC PROGRAMMING*****
Enter number of objects:
4
Enter the max capacity of knapsack:
15
Enter Weights:
9 3 2 5
Enter Profits:
20 30 25 45
Items selected are =
4
3
2
Optimal solution (Maximum Profit) = 100
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
Department of IS&E 17 VVCE, Mysoru - 02