# 0/1 Knapsack problem using Dynamic Programming Method

0 like 0 dislike
171 views

0/1 Knapsack problem using Dynamic Programming Method

### For Indian Students- INR 570/- || For International Students- \$12.99/-

S.No.

Course Name

Apply Coupon

1.

Tensorflow 2 & Keras:Deep Learning & Artificial Intelligence

Apply Coupon

2.

Computer Vision with OpenCV | Deep Learning CNN Projects

Apply Coupon

3.

Complete Machine Learning & Data Science with Python Apply Coupon

4.

Natural Language Processing-NLP with Deep Learning in Python Apply Coupon

5.

Computer Vision OpenCV Python | YOLO| Deep Learning in Colab Apply Coupon

6.

Complete Python Programming from scratch with Projects Apply Coupon

0 like 0 dislike
by Goeduhub's Expert (5.8k points)

## For Theory of 0/1 Knapsack Problem Using Dynamic Approach Click here

Java Program

import java.util.Scanner;

public class Knap1

{

static int max(int a, int b)

{

return (a > b)? a : b;

}

static int knapSack(int W, int wt[], int val[], int n)

{

int i, w;

int [][]K = new int[n+1][W+1];

for (i = 0; i <= n; i++)

{

for (w = 0; w <= W; w++)

{

if (i==0 || w==0)

K[i][w] = 0;

else if (wt[i-1] <= w)

K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]);

else

K[i][w] = K[i-1][w];

}

}

return K[n][W];

}

public static void main(String args[])

{

Scanner sc = new Scanner(System.in);

System.out.println("Enter the number of items: ");

int n = sc.nextInt();

System.out.println("Enter the items weights: ");

int []wt = new int[n];

for(int i=0; i<n; i++)

wt[i] = sc.nextInt();

System.out.println("Enter the items values: ");

int []val = new int[n];

for(int i=0; i<n; i++)

val[i] = sc.nextInt();

System.out.println("Enter the maximum capacity: ");

int W = sc.nextInt();

System.out.println("The maximum value that can be put in a knapsack of capacity W is: " + knapSack(W, wt, val, n));

sc.close();

}

Output