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()
Leave a Comment