Knapsack Problem Java

Question

• You are given a number n, representing the count of items.
• You are given n numbers, representing the values of n items.
• You are given n numbers, representing the weights of n items.
• You are given a number "cap", which is the capacity of a bag you've.
• You are required to calculate and print the maximum value that can be created in the bag without overflowing its capacity.

Note -> Each item can be taken 0 or 1 number of times. You are not allowed to put the same item again and again.

Input Format

A number n
v1 v2 .. n number of elements
w1 w2 .. n number of elements
A number cap

Output Format

A number representing the maximum value that can be created in the bag without overflowing its capacity

Constraints

1 <= n <= 20
0 <= v1, v2, .. n elements <= 50
0 < w1, w2, .. n elements <= 10
0 < cap <= 10

Sample Input

5
15 14 10 45 30
2 5 1 3 4
7

Sample Output

75

Program

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        Scanner scn = new Scanner(System.in);
        int n = scn.nextInt();
        int[] val = new int[n];
        int[] weg = new int[n];
        for(int i = 0; i < n; i++){
            val[i] = scn.nextInt();
        }
        for(int i = 0; i < n; i++){
            weg[i] = scn.nextInt();
        }
        int cap = scn.nextInt();
        int[][] dp = new int[n + 1][cap + 1];
        
        for(int i = 1; i < dp.length; i++){
            for(int j = 1; j < dp[0].length; j++){
                if(j >= weg[i - 1]){
                    int vals = dp[i - 1][j - weg[i - 1]] + val[i - 1];
                    if(vals > dp[i - 1][j]){
                        dp[i][j] = vals;
                    }
                    else{
                        dp[i][j] = dp[i - 1][j];
                    }
                }
                else{
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        System.out.println(dp[n][cap]);
    }
}