import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Knapsack {
	public static void main(String[] args) {
		System.out.println("How Many Items?");
		int numItems = new Scanner(System.in).nextInt();
		System.out.println("Max Weight?");
		int maxWeight = new Scanner(System.in).nextInt();
		char[] items = new char[numItems];
		int[] values = new int[numItems];
		int[] weights = new int[numItems];

		for (int i = 0; i < numItems; i++) {
			System.out.println((char) (65 + i));
			items[i] = (char) (65 + i);
			System.out.println("Weight: ");
			weights[i] = new Scanner(System.in).nextInt();
			System.out.println("Value: ");
			values[i] = new Scanner(System.in).nextInt();
		}

		System.out.format("+------+------+-----+%n");
		System.out.format("| Item |Weight|Value|%n");
		System.out.format("+------+------+-----+%n");
		for (int i = 0; i < numItems; i++) {
			System.out.format("| %-4s | %-4d | %-4d|%n", items[i], weights[i], values[i]);
			System.out.format("+------+------+-----+%n");
		}
		System.out.println(getItems(items, values, weights, maxWeight));
		
	}

	public static List<Character> getItems(char[] items, int[] value, int[] weight, int capacity) {
		List<Character> solution = new ArrayList<>();
		int[][] possibleSolutions = new int[items.length][capacity + 1];
		for (int j = 0; j < possibleSolutions[0].length; j++) {
			if (weight[0] <= j) {
				possibleSolutions[0][j] = weight[0];
			}
		}
		for (int i = 1; i < possibleSolutions.length; i++) {
			for (int j = 1; j < possibleSolutions[0].length; j++) {
				if (weight[i] > j) {
					possibleSolutions[i][j] = possibleSolutions[i - 1][j];
				} else {
					possibleSolutions[i][j] = Math.max(value[i] + possibleSolutions[i - 1][j - weight[i]],
							possibleSolutions[i - 1][j]);
				}
			}
		}
		int currentFilled = 0;
		for (int i = possibleSolutions.length - 1; i > 0; i--) {
			if (possibleSolutions[i][capacity - currentFilled] != possibleSolutions[i - 1][capacity - currentFilled]
					&& possibleSolutions[i][capacity - currentFilled] != 0) {
				currentFilled += weight[i];
				solution.add(items[i]);
			}
		}
		if (possibleSolutions[0][capacity - currentFilled] != 0) {
			solution.add(items[0]);
		}
		return solution;
	}

}