Q-6 PepCoding | Print All Results In 0-1 Knapsack

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

public class Main {
    public static class pair {
        int i ;
        int j ;
        String psf;
        
        pair(int i , int j , String psf){
            this.i = i;
            this.j = j;
            this.psf = psf;
        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine());

        int[] val = new int[size];
        String str1 = br.readLine();
        for (int i = 0; i < size; i++) {
            val[i] = Integer.parseInt(str1.split(" ")[i]);
        }

        int[] wts = new int[size];
        String str2 = br.readLine();
        for (int i = 0; i < size; i++) {
            wts[i] = Integer.parseInt(str2.split(" ")[i]);
        }

        int cap = Integer.parseInt(br.readLine());

        //rows will be wts-val and cols will 0 to knapsack capacity (W)
         int dp[][] = new int[size+1][cap+1];
         int m = dp.length  , n = dp[0].length;
         
         //first row and first col will be 0 by default 
         
         //rest of the array
         
         for(int i = 1 ; i <m ;i++ ){
             for(int j = 1 ; j < n;j++){
                 
                 int plays = 0; 
                 int notplays = dp[i-1][j];
                 
                 if(j >= wts[i-1])
                 plays = val[i-1] + dp[i-1][j- wts[i-1]];
                 
                 dp[i][j] = Math.max(plays , notplays);
                 
             }
         }
         
         System.out.println(dp[m-1][n-1]);
         
         BFS(dp,val , wts);
        
    }
    
    public static void BFS(int[][]dp ,int[] val, int[] wts){
        ArrayDeque<pair> q = new ArrayDeque<>();
        q.add(new pair(dp.length -1 , dp[0].length-1,""));
        
        
        while(q.size()>0){
            pair rem = q.removeFirst();
            
            int i = rem.i , j = rem.j;
            String psf = rem.psf;
            
            //if players or balls become 0 print psf
            if(i == 0 || j == 0)
            System.out.println(psf);
            
            else{
                
                //when the number plays and when it doesn't play
                int plays = 0 , notplays = dp[i-1][j];
                
                if(j >= wts[i-1])
                plays= dp[i-1][j-wts[i-1]] + val[i-1];
                
                if(plays == dp[i][j])
                q.add(new pair(i-1 , j-wts[i-1] , i-1 +" "+psf));
                
                if(notplays == dp[i][j])
                q.add(new pair(i-1 , j , psf));
                
            }
        }
    }
}