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 n = items.length;
		int maxprofit = 0;
		for (int i = 0; i < items.length; i++) {
			maxprofit += items[i].getProfit();
		}

		int a[][][] = new int[n][maxprofit + 1][maxItems + 1];

		// ganzes Array mit unendlich füllen bzw. capacity + 1
		for (int i = 0; i < n; i++) {

			for (int t = 0; t <= maxprofit; t++) {

				for (int c = 0; c <= maxItems; c++) {
					a[i][t][c] = capacity + 1;
				}

			}

		}

		for (int t = 1; t <= maxprofit; t++) {

			for (int i = 0; i < n; i++) {

				if (items[i].getProfit() == t) {
					a[i][t][1] = items[i].getWeight();
				}else if(i > 0){
					a[i][t][1] = a[i-1][t][1];
				}

			}

		}

		for(int i = 0; i < n; i++) {
			for(int t = 0; t <= maxprofit; t++) {
				a[i][t][0] = 0;
			}
		}

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

			for (int t = 0; t <= maxprofit; t++) {

				for (int c = 2; c <= maxItems; c++) {

					if (t < items[i].getProfit()) {
						a[i][t][c] = a[i - 1][t][c];
					} else {
						a[i][t][c] = Math.min(a[i - 1][t][c], a[i - 1][t - items[i].getProfit()][c - 1] + items[i].getWeight());
					}

				}

			}

		}

		int j = 0;

			for (int t = 1; t <= maxprofit; t++) {
				for (int c = 1; c <= maxItems; c++) {
					if (a[n-1][t][c] <= capacity ) {
						j = t;
					}
				}
			}

		return j;
	}

}