Skip to content

Instantly share code, notes, and snippets.

@echo-akash
Created October 5, 2017 16:10
Show Gist options
  • Save echo-akash/2216618e7f9164fa5d23a2d7879bb88e to your computer and use it in GitHub Desktop.
Save echo-akash/2216618e7f9164fa5d23a2d7879bb88e to your computer and use it in GitHub Desktop.
Finding maximum profit in 0-1 Knapsack in Java
package javalab02;
import java.util.Scanner;
public class JavaLab02 {
public static int findProfit(int i, int c, int w[], int v[], int n){
if(i==n||c==0){
return 0;
}else if(w[i]<=c){
int x1 = v[i] + findProfit(i+1,c-w[i], w, v, n);
int x2 = findProfit(i+1,c, w, v, n);
return x1>x2?x1:x2;
}else{
return findProfit(i+1,c, w, v, n);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int w[] = new int[n];
int v[] = new int[n];
int capacity = sc.nextInt();
for (int i = 0; i < w.length; i++) {
w[i] = sc.nextInt();
}
for (int i = 0; i < v.length; i++) {
v[i] = sc.nextInt();
}
System.out.println(findProfit(0, capacity, w, v, n));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment