Untitled

interface Task {
    id: string;
    numberOfBasketsNeeded: number;
}
//O(N!) :cry
// const getBestBatch0 = (maxTasksPerBatch: number, trolleyCapacity: number, tasks: Task[]): Task[] => {
//     let bestBatch: Task[] = [];
//     let bestUtilization = 0;

//     const searchBatch = (currentBatch: Task[], remainingTasks: Task[], currentBaskets: number) => {
//         if (currentBatch.length > maxTasksPerBatch || currentBaskets > trolleyCapacity) {
//             return;
//         }

//         let utilization = currentBaskets / trolleyCapacity;
//         if (utilization > bestUtilization) {
//             bestUtilization = utilization;
//             bestBatch = currentBatch.slice();
//         }

//         for (let i = 0; i < remainingTasks.length; i++) {
//             let nextTask = remainingTasks[i];
//             searchBatch([...currentBatch, nextTask], remainingTasks.slice(i + 1), currentBaskets + nextTask.numberOfBasketsNeeded);
//         }
//     };

//     searchBatch([], tasks, 0);
//     return bestBatch;
// };

// O(n*m*t)
const getBestBatch = (maxTasksPerBatch: number, trolleyCapacity: number, tasks: Task[]) => {
    const n = tasks.length;
    const dp = Array.from({ length: maxTasksPerBatch + 1 }, () => Array(trolleyCapacity + 1).fill(0));
    const keep = Array.from({ length: maxTasksPerBatch + 1 }, () => Array(trolleyCapacity + 1).fill(false));
  
    for (let i = 0; i < n; i++) {
      for (let k = maxTasksPerBatch; k >= 1; k--) {
        for (let w = trolleyCapacity; w >= tasks[i].numberOfBasketsNeeded; w--) {
          if (dp[k - 1][w - tasks[i].numberOfBasketsNeeded] + tasks[i].numberOfBasketsNeeded > dp[k][w]) {
            dp[k][w] = dp[k - 1][w - tasks[i].numberOfBasketsNeeded] + tasks[i].numberOfBasketsNeeded;
            keep[k][w] = i;
          }
        }
      }
    }

    const batch: Task[] = [];
    let w = trolleyCapacity;
    let k = maxTasksPerBatch;
  
    while (k > 0 && w > 0) {
      if (keep[k][w] !== false) {
        const taskIndex = keep[k][w];
        if(!batch.find(task=> task.id ===tasks[taskIndex].id)){
            batch.push(tasks[taskIndex]);
        }
        w -= tasks[taskIndex].numberOfBasketsNeeded;
        k--;
      } else {
        break;
      }
    }
  
    return batch;
  };



const getBatches = (maxTasksPerBatch: number, trolleyCapacity: number, tasks: Task[]): Task[][] => {
    const batches: Task[][] = [];

    while (tasks.length) {
        const batch = getBestBatch(maxTasksPerBatch, trolleyCapacity, tasks);
        batches.push(batch);
        tasks = tasks.filter(task => !batch.includes(task));
    }

    return batches;
};

//tasks
const tasks = [
    {
      "id": "23dd6749-4b69-4514-8407-a87805b950d6",
      "numberOfBasketsNeeded" : 5
    },
    {
      "id":"33dd6749-4b69-4514-8407-a87805b950d6",
      "numberOfBasketsNeeded" : 4
    },
    {
      "id": "43dd6749-4b69-4514-8407-a87805b950d6",
      "numberOfBasketsNeeded" : 3
    },
    {
      "id": "53dd6749-4b69-4514-8407-a87805b950d6",
      "numberOfBasketsNeeded" : 3
    },
    {
      "id": "63dd6749-4b69-4514-8407-a87805b950d6",
      "numberOfBasketsNeeded" : 5
    }
    ,
    {
      "id": "73dd6749-4b69-4514-8407-a87805b950d6",
      "numberOfBasketsNeeded" : 3
    }
  ]


console.log(getBatches(3, 10, tasks));