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";
}