package ads.set1.knapsack;

public class MaxItemsKnapsackSolver {
	/**
	 * Solves the limited-items knapsack problem using a dynamic programming
	 * algorithm based on the one introduced in the lecture.
	 *
	 * @param items
	 *            (possibly empty) list of items. All items have a profit
	 *            {@code > 0.}
	 * @param capacity
	 *            the maximum weight allowed for the knapsack ({@code >= 0}).
	 * @param maxItems
	 *            the maximum number of items that may be packed ({@code >= 0}).
	 * @return the maximum profit achievable by packing at most {@code maxItems}
	 *         with at most {@code capacity} weight.
	 */
	public static int pack(Item[] items, int capacity, int maxItems) {
		int itemNumber = items.length;
		int res = 0;
		//creates two 3d arrays with 0 being the profit table and 1 being the items used table
		int[][][] knapsack = new int[itemNumber][capacity + 1][2];
		// Fill knapsack with -1.
		// Set number of used items to 0.
		for (int i = 0; i < itemNumber; i++) {
			for (int j = 0; j <= capacity; j++) {
				knapsack[i][j][0] = -1;
				knapsack[i][j][1] = 0;
			}

		}
		// Fill the first row with 0.
		// Set number of used items to 0.
		for (int i = 0; i < itemNumber; i++) {
			knapsack[i][0][0] = 0;
			knapsack[i][0][1] = 0;
		}
		// Put the first item into the knapsack.
		if(items[0].getWeight() <= capacity) {
			knapsack[0][items[0].getWeight()][0] = items[0].getProfit();
			knapsack[0][items[0].getWeight()][1] = 1;
		}
		// Iterate over all items and over all possible weights.

		for (int i = 1; i < itemNumber; i++) {

			int weight = items[i].getWeight();
			int profit = items[i].getProfit();
			// Iterate over all possible weights and check if there is an entry to the left.
			// If so check if the current item would improve that entry.
			// If it does, exchange it else leave it.
			for (int j = 0; j <= capacity; j++) {
				// Checks if there is an entry on the left with less than the maxItems.
				if ((knapsack[i - 1][j][0] != -1) && knapsack[i - 1][j][1] <= maxItems) {
					// Checks if current weight would end up over the maximum capacity.
					if (j + weight <= capacity) {
						// Checks if the the current item would improve the profit when added to the
						// item constellation at [i-1][j]. If so add the item.
						if (knapsack[i - 1][j][0] + profit < knapsack[i - 1][j + weight][0]
								|| knapsack[i - 1][j + weight][0] == -1) {

							knapsack[i][j + weight][0] = knapsack[i-1][j][0] + profit;
							knapsack[i][j + weight][1] = knapsack[i-1][j][1] + 1;

						}

					}
					// Transfers entries to the next column.
					if (knapsack[i][j][0] == -1) {

						knapsack[i][j][0] = knapsack[i - 1][j][0];
						knapsack[i][j][1] = knapsack[i - 1][j][1];
					}
				}
			System.out.print(knapsack[i][j][0]); System.out.print("/");System.out.print(knapsack[i][j][1] + " ");
			}
			System.out.println("");
		}


		// Finds the highest profit possible.
		for (int i = 0; i <= capacity; i++) {
			if (res < knapsack[itemNumber - 1][i][0]) {
				res = knapsack[itemNumber - 1][i][0];
			}
		}
		return res;
	}
}