Knapsack

KnapSack.java

package com.algorithms;

import static java.lang.Math.max;

/**
 * Created by Hadi on 10/24/2016.
 */
public class KnapSack {

    public static void main(String[] args){
        int val[] = {1000, 2000, 2500, 3000};
        int wt[] = {1, 2, 3, 4};
        int W = 4;
        System.out.println(knapsack(val, wt, W));

    }

    public static int knapsack(int val[], int wt[], int W) {
        int N = wt.length;
        int[][] V = new int[N + 1][W + 1];


        for (int item=1;item<=N;item++){
            for (int weight=1;weight<=W;weight++){
                if (wt[item-1]<=weight){
                    V[item][weight] = max(val[item-1]+V[item-1][weight-wt[item-1]], V[item-1][weight]);
                } else {
                    V[item][weight] = V[item-1][weight];
                }
            }
        }
        return V[N][W];
    }
}