knapsack.java

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;


public class RedMart {
    
    static class P{
        /***
         *  This is a Product Class for composing all the 
         *  state a typical product has such as the 
         *  id, length, width, height, weight, price, etc.
         */
        int id;
        int p;
        int le;
        int wi;
        int hi;
        int w;
        
        int v; //volume
        public P(int id, int p, int le, int wi, int hi, int w){
            this.id=id;
            this.p=p;
            this.le=le;
            this.wi=wi;
            this.hi=hi;
            this.w=w;
            this.v = le*wi*hi;
        }
    }

    
    public static void main(String[] args) throws FileNotFoundException, IOException {
        
        //file IO
        String FILE_NAME = "C:\\users\\arthur\\desktop\\products.csv";
        
        BufferedReader br = new BufferedReader(new FileReader(FILE_NAME));
        
        int MAXV = 45*30*35; // max volume (45*30*35)
        int MAXN = 20000; // total number of items in Universe
        
        P[] S = new P[MAXN+1]; // an array of products objects
        
        for(int i=1;i<=MAXN;i++){
            
            String[] line = br.readLine().split(",");
            int id = Integer.parseInt(line[0]);
            int p = Integer.parseInt(line[1]);
            int le = Integer.parseInt(line[2]);
            int wi = Integer.parseInt(line[3]);
            int hi = Integer.parseInt(line[4]);
            int w = Integer.parseInt(line[5]);
            
            
            
            S[i] = new P(id,p,le,wi,hi,w);
            
        }
        
        //table of state for subproblems
        
        int[] p = new int[MAXV+1]; //for price
        int[] w = new int[MAXV+1]; //for weight
        
        int[] pid = new int[MAXV+1];
        
        Arrays.fill(p,-1);
        Arrays.fill(w,-1);
        
        Arrays.fill(pid,-1);
        p[0]=0;
        w[0]=0;
        
        pid[0]=0;
        
        for(int i=1;i<=MAXN;i++){
            //iteration i
            
            /**
             * These are for the ith row of the table
             * while p,w,pid are for the (i-1)th row
             */
            int[] n_p = new int[MAXV+1];
            int[] n_w = new int[MAXV+1];
            int[] n_pid = new int[MAXV+1];
            for(int j=1;j<=MAXV;j++){
                
                //no changes
                if(S[i].v > j){
                    n_p[j] = p[j];
                    n_w[j] = w[j];
                    n_pid[j]=pid[j];
                    //System.out.println("At Iteration "+i+" Volume "+j+" too big v of i "+S[i].v);
                }else{
                
                    /*
                     * No Combination of Items have yet to be found of total volume of j
                     */
                    if(p[j]==-1){
                        
                        if(p[j-S[i].v]==-1){
                            n_p[j] = p[j];
                            n_w[j] = w[j];
                            n_pid[j]=pid[j];
                           
                        }else{
                            n_p[j] = p[j-S[i].v] + S[i].p;
                            n_w[j] = w[j-S[i].v] + S[i].w;
                            n_pid[j]= pid[j-S[i].v] + S[i].id;
                            
                            
                        }
                    }
                    else{
                        if(p[j-S[i].v]==-1){
                            n_p[j] = p[j];
                            n_w[j] = w[j];
                            n_pid[j]=pid[j];
                            
                        }else if(p[j-S[i].v]>=0 && p[j-S[i].v]+S[i].p > p[j]){
                            n_p[j] = p[j-S[i].v] + S[i].p;
                            n_w[j] = w[j-S[i].v] + S[i].w;
                            n_pid[j]= pid[j-S[i].v] + S[i].id;
                            
                        }
                        else if(p[j-S[i].v]>=0 && p[j-S[i].v]+S[i].p == p[j] && w[j-S[i].w]+S[i].w > w[j]){
                            n_p[j] = p[j-S[i].v] + S[i].p;
                            n_w[j] = w[j-S[i].v] + S[i].w;
                            n_pid[j]= pid[j-S[i].v] + S[i].id;
                            
                        }else{
                            n_p[j] = p[j];
                            n_w[j] = w[j];
                            n_pid[j]=pid[j];
                            
                        }
                    }
                }
            }
            
            for(int j=1;j<=MAXV;j++){
                p[j]=n_p[j];
                w[j] = n_w[j];
                pid[j] = n_pid[j];
                
            }
            //System.out.println();
        }
        System.out.println(pid[MAXV]);
        
    }
}