package algoexpert.hard;

import java.util.ArrayList;

import java.util.List;

/*

PROBLEM:

Given array of items with values and weights (in order) and maximum capacity of knapsack.

Maximize value in knapsack without exceeding capacity.

- items cannot be repeated

- assume there will be only one combination of items that maximizes the total value in knapsack

Output Format -> [[max_value_within_capacity], [indexes of items chosen]]

EXAMPLE:

[ [1,2], [4,3], [5,6], [6,7] ], 10 -> [ [10], [1,3]]

LOGIC:

- item can be either added to knapsack or left out

- create a 2D array with rows representing the items until that point | col representing capacity | entry representing max_value_achievable_till

if capacity > currentWeight:

- then item can be added

- maxValue[row][col] = max (item not added, item added)

- maxValue[row][col] = max (maxValue[row - 1][col], maxValues[row - 1][c - currentWeight] + currentValue)

- in backtracking just check if we added the item or not (currentValue == value at [row - 1] or not)

SOLUTION:

1. Dynamic Programming & Backtracking (to find indexes) -> time : O(nc) | space : O(nc)

*/

public class IOKnapsack

{

public static void test()

{

int[][] testItems = { {1,2}, {4,3}, {5,6}, {6,7} };

System.out.println(knapsackProblem(testItems, 10));

int[][] input = {{1, 2}, {70, 70}, {30, 30}, {69, 69}, {100, 100}};

System.out.println(knapsackProblem(input, 100));

}

private static List<List<Integer>> generateSolution(int[][] maxValues, int[][] items)

{

List<List<Integer>> solution = new ArrayList<List<Integer>> ();

List<Integer> maxValue = new ArrayList<>();

List<Integer> indexes = new ArrayList<>();

int row = maxValues.length - 1;

int col = maxValues[0].length - 1;

maxValue.add(maxValues[row][col]);

solution.add(maxValue);

while (row > 0 && col >= 0)

{

// checks if we added the item to the knapsack?

if (maxValues[row][col] == maxValues[row - 1][col]) // not added

{

row = row - 1;

}

else // added

{

indexes.add(0, row - 1); // insert at front otherwise need to reverse

row = row - 1;

col = col - items[row][1]; // itemWeight

}

}

solution.add(indexes);

return solution;

}

// time : O(nc) | space : O(nc)

public static List<List<Integer>> knapsackProblem(int[][] items, int capacity)

{

int maxValues [][] = new int[items.length + 1][capacity+1];

for (int row = 1; row < maxValues.length; ++row)

{

int currentValue = items[row - 1][0];

int currentWeight = items[row - 1][1];

for (int c = 0; c <= capacity; ++c)

{

if (c < currentWeight)

{

// item not added

maxValues[row][c] = maxValues[row - 1][c];

}

else

{

// item can be added

maxValues[row][c] = Math.max(maxValues[row - 1][c], maxValues[row - 1][c - currentWeight] + currentValue);

}

}

}

return generateSolution(maxValues, items);

}

}