class Knapsack {
	public static void main(String[] args) throws Exception {
		//
		// 3 8.00
		// 700 7.00 299 3.00 499 5.00
		int cal[] = {700, 299, 499 };// val=cal
		double price[] = {7.00, 3.00, 5.00 };
		int max = 8;
		System.out.println(knapsack(cal, price, max));
	}

	public static int knapsack(int cal[], double price[], int maxPrice) {
		int N = price.length; // Get the total number of items. Could be price.length
							// or cal.length. Doesn't matter
		int[][] V = new int[N + 1][maxPrice + 1]; // Create a matrix. Items are in rows
											// and price at in columns +1 on
											// each side
		// What if the knapsack's capacity is 0 - Set all columns at row 0 to be
		// 0
		for (int col = 0; col <= maxPrice; col++) {
			V[0][col] = 0;
		}
		// What if there are no items at home. Fill the first row with 0
		for (int row = 0; row <= N; row++) {
			V[row][0] = 0;
		}
		for (int item = 1; item <= N; item++) {
			// Let's fill the values row by row
			for (int calories = 1; calories <= maxPrice; calories++) {
				// Is the current items cal less than or equal to running
				// cal
				if (price[item - 1] <= calories) {
					// Given a cal, check if the value of the current item +
					// value of the item that we could afford with the remaining
					// weight
					// is greater than the value without the current item itself
					V[item][calories] = Math.max(cal[item - 1]
							+ V[item - 1][(int) (calories - price[item - 1])],
							V[item - 1][calories]);
				} else {
					// If the current item's cal is more than the running
					//cal, just carry forward the value without the current
					// item
					V[item][calories] = V[item - 1][calories];
				}
			}
		}
		// Printing the matrix
		for (int[] rows : V) {
			for (int col : rows) {
				System.out.format("%5d", col);
			}
			System.out.println();
		}
		return V[N][maxPrice];
	}
}