Code made after watching class Knapsack 1 - problem formulation, dynamic programming (34:20) Course: Discrete Optimization from amazing professor Pascal Van Hentenryck

Knapsack1.java

import java.util.Arrays;

public class Knapsack1
{
	private int n; // number of itens
	private int k; // capacity
	private int[][] dp;
	private Item[] itens;
	
	private class Item implements Comparable<Item> {
		int w, v;
		public Item(int weight, int value) {
			w = weight; v = value;
		}
		public int compareTo(Item that) {
			if(v < that.v) return -1;
			if(v > that.v) return 1;
			return 0;
		}
	}
	
	public Knapsack1(int[] weights, int[] values, int capacity)
	{
		n = weights.length;
		k = capacity;
		dp = new int[k+1][n+1];
		itens = new Item[n];
		
		for(int i = 0; i < n; ++i) {
			itens[i] = new Item(weights[i], values[i]);
		}
		
		Arrays.sort(itens);

		for(int i = 1; i < dp[i].length; ++i)
			for(int c = 1; c < dp.length; ++c)
				for(int j = 0; j < i; ++j) if(itens[j].w <= c)
					dp[c][i] = Math.max(dp[c][i-1], itens[j].v + dp[c-itens[j].w][i-1]);
					
		System.out.println(dp[k][n]);
		
		printTable();
		
		traceback();
	}
	
	public void printTable()
	{
		for(int i = 0; i < dp.length; ++i) {
			for(int j = 0; j < dp[i].length; ++j) {
				System.out.printf("%2d ", dp[i][j]);
			}
			System.out.println();
		}
	}
	
	public void traceback()
	{
		for(int i = n; i > 0; --i) {
			if(dp[k][i] != dp[k][i-1]) { // it took this item
				k -= itens[i-1].w;
				System.out.printf("Item: weight = %d value = %d\n", 
						itens[i-1].w, itens[i-1].v);
			}
		}
	}
	
	public static void main(String[] args)
	{
		Knapsack1 app = new Knapsack1(
				new int[]{2,3,4,5},
				new int[]{16,19,23,28},
				7);
		
		app = new Knapsack1(
				new int[]{2,3,4,4},
				new int[]{6,9,10,8},
				7);
	}
}