Untitled

class WarehouseService {
  isDependencyAdded(selectedItems, item) {
    // Create new set
    const selectedNamesSet = new Set(
      selectedItems.map((selectedItem) => selectedItem.name)
    )

    // Check if every dependency is present in the Set
    for (let dependency of item.dependencies) {
      if (!selectedNamesSet.has(dependency)) {
        return false // Exit if a dependency is not met
      }
    }

    return true // All dependencies are met
  }

  optimizeWarehouseItems(items, totalSpace) {
    // Sort items by priority (ascending, lower number comes first)
    items.sort((a, b) => a.priority - b.priority)

    // Initialize itemsMaxValue array to store max value for each capacity
    const itemsMaxValue = new Array(totalSpace + 1).fill(0)

    // Array to store the best combination of items for each capacity
    const selectedItems = new Array(totalSpace + 1).fill(null).map(() => [])

    // Track items that have been added to avoid duplicates
    const alreadyAdded = new Array(totalSpace + 1)
      .fill(null)
      .map(() => new Set())

    // Iterate over each space capacity from 1 to totalSpace
    for (let spaceCapacity = 1; spaceCapacity <= totalSpace; spaceCapacity++) {
      let maxValue = itemsMaxValue[spaceCapacity] // Track the max value for current capacity
      let bestCombo = [...selectedItems[spaceCapacity]] // Track the best combination of items for current capacity

      // Iterate over all items (sorted by priority) using forEach
      items.forEach((item) => {
        if (item.size <= spaceCapacity) {
          // If item can fit in the current capacity
          const spaceLeft = spaceCapacity - item.size // Remaining space after including the item

          // Check if dependencies of the current item are met and the item is not already added
          if (
            this.isDependencyAdded(selectedItems[spaceLeft], item) &&
            !alreadyAdded[spaceLeft].has(item.name)
          ) {
            const potentialValue = itemsMaxValue[spaceLeft] + item.value

            if (potentialValue > maxValue) {
              maxValue = potentialValue // Update max value
              bestCombo = [...selectedItems[spaceLeft], item] // Update best combination
            }
          }
        }
      })

      itemsMaxValue[spaceCapacity] = maxValue // Update itemsMaxValue array for current capacity
      selectedItems[spaceCapacity] = bestCombo // Update selected items for current capacity

      // Update alreadyAdded items set for the current capacity
      alreadyAdded[spaceCapacity] = new Set(bestCombo.map((i) => i.name))
    }

    // Get the best combination of items and the corresponding maximum value
    const maxValue = itemsMaxValue[totalSpace]
    const bestCombination = selectedItems[totalSpace]

    return {
      maxValue,
      bestCombination
    }
  }
}

module.exports = new WarehouseService()