void KnapsackDynamic(Item* items, int itemCount, int knapsackSize)
{
	int** knapsackValues = CreateArray<int>(itemCount + 1, knapsackSize + 1);
	SetDefaultValues(knapsackValues, 0, itemCount + 1, knapsackSize + 1);

	int** knapsackWeights = CreateArray<int>(itemCount + 1, knapsackSize + 1);
	SetDefaultValues(knapsackWeights, 0, itemCount + 1, knapsackSize + 1);

	int** indexes = CreateArray<int>(itemCount + 1, knapsackSize + 1);
	SetDefaultValues(indexes, 0, itemCount + 1, knapsackSize + 1);

	int newValue{};
	int repeatedValue{};
	int knownValue{};
	int newWeight{};
	bool noRepeats = true;

	for (int i = 1; i <= itemCount; i++) {
		noRepeats = true;
		for (int j = 1; j <= knapsackSize; j++) {
			if (items[i - 1].weight <= j) {
				repeatedValue = 0;
				//check if adding another repetition of this object won't overflow knapsack
				if ((knapsackWeights[i][j - 1] + items[i - 1].weight) <= j) 
					repeatedValue = items[i - 1].price + knapsackValues[i][j - 1];

				//newValue = new item + value from previous iteration
				//items[i - 1] beacuse indexing starts from 0, so first item is on index 0
				newValue = items[i - 1].price + knapsackValues[i - 1][j - items[i - 1].weight];

				//Determine if repeating new item will give greater value than adding to previous iteration
				knownValue = max(knapsackValues[i - 1][j], knapsackValues[i][j-1]);
				
				//std::cout << knownValue << " " << repeatedValue << " " << newValue <<" "<<noRepeats<< "\n";

				int index = i;

				//if new value greater than in previous iteration and greater or equal to repetition
				//set to knapsack value and weight of new element
				if (newValue >= knownValue and newValue >= repeatedValue) {
					newWeight = items[i - 1].weight + knapsackWeights[i - 1][j - items[i - 1].weight];
					noRepeats = true;
				}

				//else if repeated value is greater than in previous iteration
				//set to knapsack value and weight of repeated item
				else if (repeatedValue >= knownValue) {
					newValue = repeatedValue;
					newWeight = items[i - 1].weight + knapsackWeights[i][j - 1];
					noRepeats = false;
				}

				else {
					//if no repeated item was added, copy values from above row
					if (noRepeats) {
						newValue = knownValue;
						if (i > 2) {
							newWeight = knapsackWeights[i - 1][j];
							index = indexes[i - 1][j];
						}
						else
						{
							newWeight = items[i - 1].weight;
						}
					}
					//if repeated item was added, copy values from cell in array on left 
					else if (knapsackValues[i][j - 1] < knapsackValues[i-1][j]) {
						newValue = knapsackValues[i-1][j];
						newWeight = knapsackWeights[i-1][j];
						index = indexes[i-1][j];
					}
					//if repeated item was added, copy values from cell in array on left 
					else {
					newValue = knapsackValues[i][j - 1];
					newWeight = knapsackWeights[i][j - 1];
					index = indexes[i][j - 1];
				}
				}

				knapsackValues[i][j] = newValue;
				knapsackWeights[i][j] = newWeight;
				indexes[i][j] = index;

				//ShowArray(knapsackValues[i], knapsackSize + 1, 3);
				//ShowArray(knapsackWeights[i], knapsackSize + 1, 3);
				
			}
			//if item too large copy values from above
			else {
				knapsackValues[i][j] = knapsackValues[i - 1][j];
				knapsackWeights[i][j] = knapsackWeights[i - 1][j];
				indexes[i][j] = indexes[i - 1][j];
			}
		}

		//std::cout << "\n";
	}
	std::cout << "Values: \n";
	ShowArray(knapsackValues, itemCount + 1, knapsackSize + 1, 3);

	std::cout << "Weights: \n";
	ShowArray(knapsackWeights, itemCount + 1, knapsackSize + 1, 3);

	std::cout << "Indexes: \n";
	ShowArray(indexes, itemCount + 1, knapsackSize + 1, 3);

	int sizeLeft = knapsackSize;
	int index = indexes[itemCount][sizeLeft];
	std::cout << "Items: \n";
	while (sizeLeft > 0 and indexes[itemCount][sizeLeft] != 0) {
		//std::cout<< index<<" "<< items[index-1].weight<<" "<< sizeLeft;
		index = indexes[itemCount][sizeLeft];
		std::cout <<"\t- " <<items[index-1].name<<"\n";
		sizeLeft -= items[index-1].weight;
	}
	std::cout << "\n";

}